浅谈用极大化思想解决最大子矩形问题（王知昆）
上述论文是2003年ioi国家集训队的大佬写的论文，里面详细描述了极大化思想和悬线法的运用，解决了一类求最大子矩阵的问题
本题可以利用论文中的思想来解
这道题求解的是最大的矩形和正方形，保证没有相邻的两个点颜色相同，论文中的障碍点也就是本题中向外扩展的碰到的相邻的点，本题的障碍点不可以在边界上。
下面的解题思路基于悬线法，所以不再阐述悬线法的原理。
dp思想是设计一个up数组，表示往上最多能到的地方，left数组表示向左，right表示向右，都可以通过隔壁或者上面的点递推出来。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<functional> #include<string> #include<algorithm> #include<iostream> #include<set> #include<vector> #include<queue> #include<cstdlib> using namespace std; const int N=2020; int l[N][N],r[N][N]; int up[N][N]; int f[N][N]; int a[N][N]; int ans1,ans2; int main(){ int i,j,k; int n,m; cin>>n>>m; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>a[i][j]; l[i][j]=r[i][j]=j; up[i][j]=1; } } for(i=1;i<=n;i++){ for(j=2;j<=m;j++){ if(a[i][j]!=a[i][j-1]) l[i][j]=l[i][j-1]; } } for(i=1;i<=n;i++){ for(j=m-1;j>=1;j--){ if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1]; } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(i>1&&a[i][j]!=a[i-1][j]){ up[i][j]=up[i-1][j]+1; l[i][j]=max(l[i][j],l[i-1][j]); r[i][j]=min(r[i][j],r[i-1][j]); } int a=r[i][j]-l[i][j]+1; int b=min(up[i][j],a); ans1=max(ans1,b*b); ans2=max(ans2,up[i][j]*a); } } cout<<ans1<<endl; cout<<ans2<<endl; }