这道题数据范围很小，所以一开始我采用极暴力手段，直接枚举所有正方形，二维前缀和暴力判断即可。后来发现可以二分，也可以从大到小，其实没什么优化。
之后想到以前做DP的时候的悬线法，就故技重施用O（n^2）的做法过了此题。
但是其实正解非常简单，用dp[i][j]表示以（i，j）为左下角的最大的符合正方形的边长。那么dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1.取min的原因是这三个方向必须同时满足，所以必须取min。
看一下悬线法的代码（正解太短了?）
#include#include #include #include #include #include #include #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')using namespace std;typedef long long ll;const int M = 105;const int INF = 1000000009;int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}int n,m,l[M][M],r[M][M],up[M][M],g[M][M],ans;int main(){ n = read(),m = read(); rep(i,1,n) rep(j,1,m) g[i][j] = read(),l[i][j] = r[i][j] = j,up[i][j] = 1; rep(i,1,n) rep(j,2,m) if(g[i][j-1] != 0) l[i][j] = l[i][j-1]; rep(i,1,n) per(j,m,2) if(g[i][j+1] != 0) r[i][j] = r[i][j+1]; rep(i,1,n) { rep(j,1,m) { if(i > 1 && g[i-1][j] != 0) { l[i][j] = max(l[i][j],l[i-1][j]); r[i][j] = min(r[i][j],r[i-1][j]); up[i][j] = up[i-1][j]+1; } int len = min(r[i][j] - l[i][j] + 1,up[i][j]); ans = max(ans,len); } } printf("%d\n",ans); return 0;}