链接：Luogu-P1169
题意
在一个$N \times M$的矩阵内，找出最大的、像国际象棋棋盘一样黑白交错的正方形和矩形。
思路
看到第一问，显然可以用二维平面DP完成：考虑设计状态$f(i,j,k)$：以$(i,j)$为右下角的最大正方形。k=1表示在这个正方形中$(i,j)$为黑，反之$(i,j)$为白。因为要求黑白交错，所以把黑白也加入状态。
于是可以转移：
$f(i,j,k)=\min \left\{f(i-1,j-1,k),f(i-1,j,\neg k),f(i,j-1,\neg k)\right\}+1$
但是第二问就不好应用二维平面DP完成了，因为一般来说二维平面DP只用于正方形。
有这样一个技巧:把横纵坐标奇偶性不同的点颜色取反，然后用悬线法求最大子矩形就行了。同理，还原成原来的矩阵后，再把横纵坐标奇偶性相同的点颜色取反，然后再做一遍悬线法，即可得到1、2问的答案。
实现
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define CLEAR(x) memset(x,0,sizeof(x))
#define SETINF(x) memset(x,0x3f,sizeof(x))
#define pow2(x) ((x)*(x))
using namespace std;
const int MAXN = 2000;
int N,M,Ans1,Ans2,W[MAXN+10][MAXN+10],lc[MAXN+10][MAXN+10],rc[MAXN+10][MAXN+10],
l[MAXN+10][MAXN+10],r[MAXN+10][MAXN+10],h[MAXN+10][MAXN+10];
inline int readint(){
int f=1,r=0;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
while(isdigit(c)){r=r*10+c-'0';c=getchar();}
return f*r;
}
inline void work(){
CLEAR(lc);CLEAR(rc);CLEAR(h);SETINF(l);SETINF(r);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
lc[i][j]=(W[i][j]?0:lc[i][j-1]+1);
for(int i=1;i<=N;i++)
for(int j=M;j>=1;j--)
rc[i][j]=(W[i][j]?0:rc[i][j+1]+1);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
h[i][j]=(W[i][j]?0:h[i-1][j]+1);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
if(!W[i][j]){
l[i][j]=min(l[i-1][j],lc[i][j]);
r[i][j]=min(r[i-1][j],rc[i][j]);
}
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++) {
Ans1=max(Ans1, pow2( min(r[i][j]+l[i][j]-1, h[i][j]) ));
Ans2=max(Ans2, (r[i][j]+l[i][j]-1)*h[i][j]);
}
}
int main(){
N=readint();M=readint();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
W[i][j]=readint();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
W[i][j]^=((i^j)&1);
work();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++) {
W[i][j]^=((i^j)&1);
W[i][j]^=(~((i^j)&1))&1;
}
work();
printf("%d\n%d",Ans1,Ans2);
}
