悬线法

 

部分内容参考Santiego的博客，侵删！侵删！侵删！

---

 

0x00 关于悬线法

只是因为这题用到了不然我干嘛写它

用于求满足某种状态的矩形，如最大01交替矩阵

0x10 简单思想

先预处理出ml[i][j],mr[i][j],mt[i][j]，分别表示当前位置(i,j)能向左扩展到的最左边的编号、能向右扩展到的最右边的编号、能向上扩展到的最大高度。

然后在做DP时，除第一行，每行根据上一行的状态更新当前状态，逐行扫一遍。复杂度O(n×m)

0x20 一些题

Luogu P2701 巨大的牛棚Big Barn

Luogu P1169 棋盘制作

Luogu P4147 玉蟾宫

0x30 题解（正文）

求01交替的最大矩形和正方形

那这题就显然了

code

 1 //
 2 //  main.cpp
 3 //  bzoj
 4 //
 5 //  Created by gengyf on 2019/7/28.
 6 //  Copyright © 2019 yifan Geng. All rights reserved.
 7 //
 8 
 9 #include <bits/stdc++.h>
10 using namespace std;
11 namespace gengyf{
12 #define ll long long
13     const int maxn=2005;
14     inline int read(){
15         int f=1,x=0;char s=getchar();
16         while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
17         while(isdigit(s)){x=x*10+s-'0';s=getchar();}
18         return x*f;
19     }
20     int n,m,ml[maxn][maxn],mr[maxn][maxn],mt[maxn][maxn];
21     int ans1,ans2,mp[maxn][maxn];
22     void init(){//预处理
23         for(int i=1;i<=n;i++)
24             for(int j=2;j<=n;j++){//向左
25                 if(mp[i][j]!=mp[i][j-1])
26                     ml[i][j]=min(ml[i][j-1],ml[i][j]);
27             }
28         for(int i=1;i<=n;i++)
29             for(int j=m-1;j>=1;j--){//向右
30                 if(mp[i][j]!=mp[i][j+1])
31                     mr[i][j]=max(mr[i][j+1],mr[i][j]);
32             }
33     }
34     int main(){
35         n=read();m=read();
36         for(int i=1;i<=n;i++)
37             for(int j=1;j<=m;j++){
38                 mp[i][j]=read();
39                 ml[i][j]=mr[i][j]=j;
40                 mt[i][j]=1;
41             }
42         init();//预处理向左右扩展
43         for(int i=1;i<=n;i++)
44             for(int j=2;j<=m;j++){// 除第一行，每行根据上一行的状态更新当前状态
45                 if(i>1&&mp[i][j]!=mp[i-1][j]){
46                     ml[i][j]=max(ml[i][j],ml[i-1][j]);
47                     mr[i][j]=min(mr[i][j],mr[i-1][j]);
48                     mt[i][j]=mt[i-1][j]+1;
49                 }
50                 int w=mr[i][j]-ml[i][j]+1;
51                 int h=mt[i][j];
52                 ans1=max(min(w,h)*min(w,h),ans1);//正方形，众所周知，正方形的长=宽
53                 ans2=max(w*h,ans2);//矩形
54             }
55         printf("%d %d\n",ans1,ans2);
56         return 0;
57     }
58 }
59 signed main() {
60     gengyf::main();
61     return 0;
62 }

View Code

 

 

 

 

 

所以，标签的单调栈在哪里？？？

嗯，不知