Submit: 3601 Solved: 1855
[Submit][Status][Discuss]
Description
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源
于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，
正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定
将棋盘扩大以适应他们的新规则。小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种
颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。不过小Q还没有决定是找
一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他
希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。于是小Q找到了即将参加全
国信息学竞赛的你，你能帮助他么？
Input
第一行包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形
纸片的颜色（0表示白色，1表示黑色）。
Output
包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋
盘的面积（注意正方形和矩形是可以相交或者包含的）。
Sample Input
3 3
1 0 1
0 1 0
1 0 0
1 0 1
0 1 0
1 0 0
Sample Output
4
6
6
HINT
N, M ≤ 2000
单调栈：
首先一个巧妙的处理，将0/1相间转化为同色，于是变成了最大子矩阵问题
设f[i][j]表示第i行第j列的点，向右最多延申多少个位置
我们可以发现最大子矩阵的宽一定是某一个f[i][j]
接下来枚举每一列，用单调栈处理，储存栈顶的f[i][j]和高度（行号），如果某一个点的f[i][j]值小于等于栈顶的f值，于是我们更新答案，后面的矩阵都不会以栈顶的f值为宽，但可能会以栈顶的高度为高，因此高度我们需要另外存储。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<stack> 5 using namespace std; 6 7 #define sqr(x) ((x)*(x)) 8 9 int n,m,ans1,ans2; 10 int a[2005][2005],f[2005][2005]; 11 int row[2005],col[2005],top,high; 12 13 void work() 14 { 15 for(int i=1;i<=n;i++) 16 for(int j=m;j>=1;j--) 17 f[i][j]=a[i][j]?f[i][j+1]+1:0; 18 for(int j=1;j<=m;j++) 19 { 20 top=0; 21 for(int i=1;i<=n+1;i++)//特别注意bzoj数据比较水 22 { 23 high=i; 24 while(top>0&&f[i][j]<=row[top]) 25 { 26 ans1=max(ans1,sqr(min(row[top],i-col[top]))); 27 ans2=max(ans2,row[top]*(i-col[top])); 28 high=col[top]; 29 top--; 30 } 31 row[++top]=f[i][j];col[top]=high; 32 } 33 } 34 } 35 36 int main() 37 { 38 scanf("%d %d",&n,&m); 39 for(int i=1;i<=n;i++) 40 for(int j=1;j<=m;j++) 41 { 42 scanf("%d",&a[i][j]); 43 if((i+j)&1) a[i][j]^=1; 44 } 45 work(); 46 for(int i=1;i<=n;i++) 47 for(int j=1;j<=m;j++) 48 a[i][j]=!a[i][j]; 49 work(); 50 printf("%d ",ans1); 51 printf("%d ",ans2); 52 return 0; 53 }
悬线法：
待填坑