正题

题目链接:/problemnew/show/P1169

题目大意

一个矩阵中求一个最大的子矩阵和子正方形使得它们其中都是01交错。

解题思路

lefti,jleft_{i,j}lefti,j​表示(i,j)(i,j)(i,j)往左扩展多远，righti,jright_{i,j}righti,j​表示(i,j)(i,j)(i,j)往右扩展多远，upi,jup_{i,j}upi,j​表示(i,j)(i,j)(i,j)向上扩展多少个。

然后对于每个点作为最下边的点时答案为

leni,j=upi,j+max{leftk,j,rightk,j}(j−k&lt;upi,j)len_{i,j}=up_{i,j}+max\{left_{k,j},right_{k,j}\}(j-k&lt;up_{i,j})leni,j​=upi,j​+max{leftk,j​,rightk,j​}(j−k<upi,j​)

ans1=upi,j∗leni,jans1=up_{i,j}*len_{i,j}ans1=upi,j​∗leni,j​

ans2=min{upi,j,leni,j}2ans2=min\{up_{i,j},len_{i,j}\}^2ans2=min{upi,j​,leni,j​}2

codecodecode

// luogu-judger-enable-o2#include<cstdio>#include<algorithm>using namespace std;const int N=2100;int n,m,a[N][N],right[N][N],left[N][N],up[N][N],ans1,ans2;int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=m;j>=1;j--){right[i][j]=(a[i][j]!=a[i][j+1]?right[i][j+1]:j);if(j==m) right[i][j]=m;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){left[i][j]=(a[i][j]!=a[i][j-1]?left[i][j-1]:j);if(j==1) left[i][j]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){up[i][j]=1;if(i>1&&a[i][j]!=a[i-1][j]){left[i][j]=max(left[i][j],left[i-1][j]);right[i][j]=min(right[i][j],right[i-1][j]);up[i][j]=up[i-1][j]+1;}int l=right[i][j]-left[i][j]+1;int w=min(up[i][j],l); ans1=max(l*up[i][j],ans1);ans2=max(w*w,ans2);}printf("%d\n%d",ans2,ans1);}