题目大意：给出一个由01形成的矩阵，问这个矩阵中最大面积的正方形和矩形，其中任意一个方块相邻的都是不同的格子，
BZOJ 1057 ZJOI 2007 棋盘制作 DP+悬线法
。思路：其实吧所有(i + j)&1的位置上的数字异或一下，就变成都是0或者都是1的最大正方形和矩形了。第一问就是水DP，第二问可以单调栈或者悬线。都很好写。
CODE：
#include<cstdio>#include<cstring>#include<iostream>#include #define MAX 2010using namespace std;int m,n;int src[MAX][MAX];int f[MAX][MAX];int up[MAX][MAX],_left[MAX][MAX],_right[MAX][MAX];int main(){ cin >> m >> n; for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) { scanf("%d",&src[i][j]); if((i + j)&1) src[i][j] ^= 1; } int ans = 0; for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) if(src[i][j]) { f[i][j] = min(f[i - 1][j - 1],min(f[i - 1][j],f[i][j - 1])) + 1; ans = max(ans,f[i][j]); } memset(f,0,sizeof(f)); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) if(!src[i][j]) { f[i][j] = min(f[i - 1][j - 1],min(f[i - 1][j],f[i][j - 1])) + 1; ans = max(ans,f[i][j]); } cout << ans * ans << endl; ans = 0; for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) _left[i][j] = src[i][j] ? _left[i][j - 1] + 1:0; for(int j = n; j; --j) _right[i][j] = src[i][j] ? _right[i][j + 1] + 1:0; } for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) if(src[i][j] && src[i - 1][j]) { up[i][j] = up[i - 1][j] + 1; _left[i][j] = min(_left[i][j],_left[i - 1][j]); _right[i][j] = min(_right[i][j],_right[i - 1][j]); ans = max(ans,(_left[i][j] + _right[i][j] - 1) * (up[i][j] + 1)); } memset(_left,0,sizeof(_left)); memset(_right,0,sizeof(_right)); memset(up,0,sizeof(up)); for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) _left[i][j] = src[i][j] ? 0:_left[i][j - 1] + 1; for(int j = n; j; --j) _right[i][j] = src[i][j] ? 0:_right[i][j + 1] + 1; } for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) if(!src[i][j] && !src[i - 1][j]) { up[i][j] = up[i - 1][j] + 1; _left[i][j] = min(_left[i][j],_left[i - 1][j]); _right[i][j] = min(_right[i][j],_right[i - 1][j]); ans = max(ans,(_left[i][j] + _right[i][j] - 1) * (up[i][j] + 1)); } cout << ans << endl; return 0;}</iostream></cstring></cstdio>