参考：https://blog.csdn.net/twtsa/article/details/8120269
先给出题目来源：(洛谷)
......
悬线法，很好理解，就是悬一根线晃来晃去求最大子矩阵嘛！
思路和转移方程也很简单：
if(满足^&%$!@#^%){ right[i][j]=min(right[i][j],right[i-1][j]); left[i][j]=max(left[i][j],left[i-1][j]); up[i][j]=up[i-1][j]+1; }
下面解释一下：
right表示从(i,j)这个点出发向右能到达最远的距离
left和up差不多，一个向左，一个向上
关于初始化
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) right[i][j]=left[i][j]=j,up[i][j]=1; for(int i=1;i<=n;i++) for(int j=2;j<=m;j++) if(满足条件) right[i][j]=right[i][j-1]; for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) if(满足条件) left[i][j]=left[i][j+1];
其实这个东西跟模板一样套就好了
【NO.1】最大正方形
【解法1】
数据这么小，考虑暴力：
维护矩阵二维前缀和，暴力枚举左上角和正方形的长，判断该块矩阵和是否为长*长，更新最大值
复杂度：O（n^3）
(很久以前以前写的代码，可能有点丑)
#include<iostream> #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; int n,m,map[105][105]; int sum[105][105]; void pre(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j]; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); pre(); int ans=-1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int l=1;l<=min(n,m);l++){ int rx=i+l-1,ry=j+l-1; if(i-1+l>n||j-1+l>m||sum[rx][ry]-sum[rx][j-1]-sum[i-1][ry]+sum[i-1][j-1]!=l*l) break; if(ans<l) ans=l; } printf("%d",ans); return 0; }【缺点】但是如果n=5000之类稍微大一点的数据就GG了，所以接下来我们用悬线法解决这个问题
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ char chr=getchar(); int f=1,ans=0; while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} return ans*f; } void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,m,a[4005][4005]; int l[4005][4005],r[4005][4005],up[4005][4005],ans1,ans2; int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),l[i][j]=r[i][j]=j,up[i][j]=1; for(int i=1;i<=n;i++) for(int j=2;j<=m;j++) if(a[i][j]==a[i][j-1]&&a[i][j]==1) l[i][j]=l[i][j-1]; for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) if(a[i][j]==a[i][j+1]&&a[i][j]==1) r[i][j]=r[i][j+1];//预处理 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(i>1) if(a[i][j]==a[i-1][j]&&a[i][j]==1){//满足条件 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 a=r[i][j]-l[i][j]+1; int b=min(a,up[i][j]); ans1=max(b,ans1);//更新答案 } cout<<ans1; return 0; }
有没有发现，其实就是模板里面把条件加上去就OK了，惊不惊喜！！！哈哈哈（其实好像下面大部分都是这样的）比如下面这题
【NO.2】棋盘制作
一样是套模板，改一下条件
注意到该题条件是10间隔分布，则if语句中内容应为：if(a[i][j]!=a[i-1][j])注意这里还有一个大前提就是i>1!
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ char chr=getchar(); int f=1,ans=0; while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} return ans*f; } void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,m,a[4005][4005]; int l[4005][4005],r[4005][4005],up[4005][4005],ans1,ans2; int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),l[i][j]=r[i][j]=j,up[i][j]=1; for(int i=1;i<=n;i++) for(int j=2;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-1;j>=1;j--) if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(i>1) if(a[i][j]!=a[i-1][j]){ 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 a=r[i][j]-l[i][j]+1; int b=min(a,up[i][j]); ans1=max(b*b,ans1); ans2=max(a*up[i][j],ans2); } cout<<ans1<<"\n"<<ans2; return 0; }
【NO.3】巨大的牛棚
还是模板？只不过读入的时候转换一下就好了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ char chr=getchar(); int f=1,ans=0; while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} return ans*f; } void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,T; int a[1005][1005],l[1005][1005],r[1005][1005],u[1005][1005],ans; int main(){ n=read();T=read(); for(int i=1;i<=T;i++){int x=read(),y=read();a[x][y]=1;} for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) l[i][j]=r[i][j]=j,u[i][j]=1; for(int i=1;i<=n;i++) for(int j=2;j<=n;j++) if(a[i][j]==0&&a[i][j-1]==0) l[i][j]=l[i][j-1]; for(int i=1;i<=n;i++) for(int j=n-1;j>=1;j--) if(a[i][j]==0&&a[i][j+1]==0) r[i][j]=r[i][j+1]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i>1&&a[i][j]==0&&a[i-1][j]==0){ u[i][j]=u[i-1][j]+1; l[i][j]=max(l[i-1][j],l[i][j]); r[i][j]=min(r[i-1][j],r[i][j]); } int a=r[i][j]-l[i][j]+1; int b=min(a,u[i][j]); ans=max(ans,b); } cout<<ans; return 0; }
【NO.4】玉蟾宫
这些题几乎一样...都不想说什么了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ char chr=getchar(); int f=1,ans=0; while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} return ans*f; } void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,m; char a[4005][4005]; int l[4005][4005],r[4005][4005],up[4005][4005],ans1,ans2; int main(){ n=read(),m=read(); 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=2;j<=m;j++) if(a[i][j]==a[i][j-1]&&a[i][j]=='F') l[i][j]=l[i][j-1]; for(int i=1;i<=n;i++) for(int j=m-1;j>=1;j--) if(a[i][j]==a[i][j+1]&&a[i][j]=='F') r[i][j]=r[i][j+1]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(i>1) if(a[i][j]==a[i-1][j]&&a[i-1][j]=='F'){ 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 a=r[i][j]-l[i][j]+1; int b=min(a,up[i][j]); ans2=max(a*up[i][j],ans2); } cout<<ans2*3; return 0; }
京公网安备 11010502036488号