悬线法-最大子矩形
介绍：
悬线法大部分情况用来处理 0-1 矩阵。先说一下各种定义——
- 有效子矩形：满足要求的子矩形
- 极大子矩形：无法再向外拓展的有效子矩形
- 最大子矩形：最大的一个有效子矩形
- 注意：在一个有障碍点的矩形中，最大子矩形一定是极大子矩形
（注：选自知乎-JC Zhang）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。这种方法其实可以从字面意思理解，既然我们要找一个最大子矩形，那不就是用一根物理上
的悬线，它永远竖直向下，然后我们可以向左右拓展，直到左边到底，右边也到极限为止。
但我们也要注意，悬线拓展出来的不一定是极大子矩形，因为悬线长度不是固定的吗?所以
我们可以枚举多条悬线嘛。。。
详细思路：
h[i][j] 表示以i，j这个点的高（或者说i，j所在直线以i，j为垂心的高）
l[i][j] 表示在第i行上最大能拓展到左边哪个位置
r[i][j] 表示在第i行上最大能拓展到右边哪个位置
首先我们应该去初始化，即每一个点（含1）高度初始化为1，且每一行的点要初始化其最左边
到达第一个障碍点的位置的1和最右边到达第一个障碍点的位置的1
h[i][j]如果此时它上面是有1的，且它本身是个1，那么我们就可以增加悬线的长度，即
h[i][j]=h[i-1][j]+1;
l取最左端的点就是要取最接近中间的，那就是取最大值，
而r取最右端的点也同理，那就取最小值
即：
l[i][j]=max(l[i][j],l[i-1][j])
r[i][j]=min(r[i][j],r[i-1][j])
这有点像那个左右压缩方块，切掉一些凸出来的罢了
用例题来说吧
https://www.luogu.com.cn/problem/P4147
我们可以将其转化为01矩阵，再找极大子矩形
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const long long N=1010; ll n,m; char c; ll a[N][N],h[N][N],l[N][N],r[N][N]; int main(){ scanf("%lld%lld",&n,&m); for( ll i=1;i<=n;i++) for( ll j=1;j<=m;j++){ c=getchar(); while(c!='R' && c!='F') c=getchar(); if(c=='F') a[i][j]=1; h[i][j]=1; l[i][j]=r[i][j]=j; } for( ll i=1;i<=n;i++){ for( ll j=2;j<=m;j++) if(a[i][j-1] && a[i][j]) l[i][j]=l[i][j-1]; for( ll j=m-1;j>=1;j--) if(a[i][j+1] && a[i][j]) r[i][j]=r[i][j+1]; } ll ans=0; for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++){ if(a[i][j] && a[i-1][j] && i>1) { l[i][j]=max(l[i][j],l[i-1][j]); r[i][j]=min(r[i][j],r[i-1][j]); h[i][j]=h[i-1][j]+1; } ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]); } ans=ans*3; printf("%lld",ans); }
更多精彩
