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