题目要求纵横坐标和奇偶性不同的点取值不同，于是我们把纵横坐标和奇偶性为1的点和0的点分别取反，就变成经典的最大全1子矩阵问题了，用悬线法解决。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int maxn=2010,inf=1e9; int n,m,ans1,ans2; int h[maxn],mp[maxn][maxn],l[maxn],r[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int sqr(int x){return x*x;} void dp() { memset(h,0,(m+1)<<2); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) if(mp[i][j])h[j]++;else h[j]=0; for(int j=1;j<=m;j++) if(mp[i][j]) for(l[j]=j;h[j]<=h[l[j]-1]&&mp[i][l[j]-1];l[j]=l[l[j]-1]); for(int j=m;j;j--) if(mp[i][j]) for(r[j]=j;h[j]<=h[r[j]+1]&&mp[i][r[j]+1];r[j]=r[r[j]+1]); for(int j=1;j<=m;j++) ans1=max(ans1,(r[j]-l[j]+1)*h[j]); for(int j=1;j<=m;j++) ans2=max(ans2,min(sqr(r[j]-l[j]+1),sqr(h[j]))); } } int main() { read(n);read(m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(mp[i][j]),mp[i][j]=((i+j)&1?mp[i][j]:!mp[i][j]); dp(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)mp[i][j]=!mp[i][j]; dp(); printf("%d %d",ans2,ans1); }