见题：
很水的一题，数据范围太小，前缀和加爆搜就行.
#include<bits/stdc++.h> using namespace std; const int maxn=110; int ans=1,m,n,sum[maxn][maxn]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) { if(ch==‘-‘) ff=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*ff; } inline void put(int x) { if(x<0) putchar(‘-‘),x=-x; if(x>9) put(x/10); putchar(x%10+‘0‘); } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x=read(); sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x; } } for(int len=2;len<=min(n,m);len++) { int he=len*len; for(int x1=1;x1<=n-len+1;x1++) { for(int y1=1;y1<=m-len+1;y1++) { int x2=x1+len-1; int y2=y1+len-1; if((sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1])==he) ans=len; } } } put(ans); return 0; }
可是还是想写正解，DP；
对于这类的二维DP，个人理解就是如果保存的从起点到终点的状态会被一些情况所中断，就要只考虑最下角的点所保存的点的状态，例如此题，我们可以保存以（i,j）为右下角的状态，以f[i][j]保存以(i,j)为最右下角的最大正方形边长.状态转移怎么样呢？
这是我们我们可以轻易的想起二维的前缀和：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j],那这个能否用前缀和处理呢，见下图：
最右下的小矩阵代表（i，j）可以很清楚地看出由左边的点，上边的点，左上角的点三个点的最小矩阵构成以个完整的矩阵，即：if(a[i][j]==1) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
这也提醒我们min的意义就是几个状态都具备的共同元素.
#include<bits/stdc++.h> using namespace std; const int maxn=110; int m,n,a[maxn][maxn],f[maxn][maxn],ans; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) { if(ch==‘-‘) ff=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*ff; } int put(int x) { if(x<0) putchar(‘-‘),x=-x; if(x>9) put(x/10); putchar(x%10+‘0‘); } inline void DP() { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]==1) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1; ans=max(ans,f[i][j]); } } } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) a[i][j]=read(); } DP(); put(ans); return 0; }
原文：https://www.cnblogs.com/gcfer/p/10747207.html