这是一道dp好题
废话不多说，看看题目意思
这道题又运用了前缀与预处理的思想
我们看着代码来解释
先解释一下各个数组的意思
l[i][j]表示i，j这个点向左拓展能满足条件的最远的点的位置
r[i][j]表示i，j这个点向右拓展能满足条件的最远的点的位置
s[i][j]表示i，j这个点向上拓展能满足条件的最大长度
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <algorithm> 5 #include <cstring> 6 #include <cmath> 7 using namespace std; 8 const int N=2005; 9 int d[N][N],s[N][N],l[N][N],r[N][N],ans1,ans2,n,m; 10 int main() 11 { 12 scanf("%d %d",&n,&m); 13 for(int i=1;i<=n;i++) 14 { 15 for(int j=1;j<=m;j++) 16 { 17 scanf("%d",&d[i][j]); 18 l[i][j]=r[i][j]=j;//每个点的左右先设置成自己 19 s[i][j]=1;//先设置成1 20 } 21 } 22 for(int i=1;i<=n;i++) 23 for(int j=2;j<=m;j++) 24 { 25 if(d[i][j]!=d[i][j-1]) 26 l[i][j]=l[i][j-1];//处理左边 27 } 28 for(int i=1;i<=n;i++) 29 for(int j=m-1;j>0;j--) 30 { 31 if(d[i][j]!=d[i][j+1]) 32 r[i][j]=r[i][j+1];//处理右边 33 } 34 for(int i=1;i<=n;i++) 35 for(int j=1;j<=m;j++) 36 { 37 if(i>1 && d[i][j]!=d[i-1][j]) 38 { 39 s[i][j]=s[i-1][j]+1;//计算上方满足条件的最大长度 40 r[i][j]=min(r[i][j],r[i-1][j]);//计算左边能到达的最远地方 41 l[i][j]=max(l[i][j],l[i-1][j]);//计算右边能到达的最远地方 42 } 43 int temp1=r[i][j]-l[i][j]+1;//计算横向长度 44 int temp2=min(temp1,s[i][j]);//比较横向长度于纵向长度哪一个长 45 int temp3=s[i][j]; 46 ans1=max(ans1,temp2*temp2);//正方形的面积 47 ans2=max(ans2,temp1*temp3);//长方形的面积 48 } 49 printf("%d %d",ans1,ans2); 50 }
代码注释已经很详细了
是一道好题啊