先是传送门:https://www.luogu.com.cn/problem/P1387
这题其实不一定要悬线法(主要是我一看到题目就想到了)
这题实质是要求图里最大正方形(没错,就是我之前的模板)
首先是暴力打法:求二维前缀和,再一波操作
二维前缀和:f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
#include <bits/stdc++.h> using namespace std; int a[105][105]; int f[105][105]; int main() { int n,m,s,ans=0; cin>>n>>m; s=min(n,m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j],f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=ans;k<=s;k++) { int x=i+k-1; int y=j+k-1; if(x>n || y>m || f[i-1][j-1]-f[x][j-1]-f[i-1][y]+f[x][y]!=k*k) break; if(ans<k) ans=k; } cout<<ans; return 0; }
同样,你也可以用普通的DP
公式也很好推:if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
#include <iostream> #include <cstdio> using namespace std; int a[101][101],n,m,f[101][101],ans; 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]); if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1; ans=max(ans,f[i][j]); } printf("%d",ans); }
最后就是悬线法了
#include <bits/stdc++.h> using namespace std; int a[105][105],l[105][105],r[105][105],up[105][105]; int main() { int n,m,ans=0; cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; l[i][j]=r[i][j]=j; up[i][j]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j] && a[i][j-1]) l[i][j]=l[i][j-1]; for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) if(a[i][j] && a[i][j+1]) r[i][j]=r[i][j+1]; for(int i=2;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i][j]==a[i-1][j]==1) { l[i][j]=max(l[i][j],l[i-1][j]); r[i][j]=min(r[i-1][j],r[i][j]); up[i][j]=up[i-1][j]+1; } int s=min(up[i][j],(r[i][j]-l[i][j]+1))*min(up[i][j],(r[i][j]-l[i][j]+1));//这里主要是求正方形,悬线法的强大无法真正体现 ans=max(ans,s);//矩形的话直接就 ans=max(ans,up[i][j]*(r[i][j]-l[i][j]+1)) } cout<<sqrt(ans); return 0; }