【学习笔记】悬线法(未完)
前言
遇到一道DP题不会做
题解有一篇是顾z大佬的（我喜欢这种大佬QAQ，看他的博客是真的能学到东西的）
说需要用悬线法写，于是干脆学一下QAQ
应用
求满足条件的最大子矩阵（当然求最大正方形加个约束就行了
例题
个人感觉写几道题大概就能搞懂它QAQ
T1
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m;
int ans1,ans2;
int a[N][N];
int l[N][N],r[N][N],up[N][N];
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);
l[i][j]=r[i][j]=j;
}
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 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++)
{
up[i][j]=1;
if(i>1&&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(ans1,b*b);
ans2=max(ans2,a*up[i][j]);
}
printf("%d\n%d",ans1,ans2);
return 0;
}
T2
tip：以上题目可用悬线法写，下面这种只求正方形的还有另一种写法