介紹：
懸線法大部分情況用來處理 0-1 矩陣，先說一下各種定義——
- 有效子矩形：滿足要求的子矩形
- 極大子矩形：無法再向外拓展的有效子矩形
- 最大子矩形：最大的一個有效子矩形
- 注意：在一個有障礙點的矩形中，最大子矩形一定是極大子矩形
（注：選自知乎-JC Zhang）
這種方法其實可以從字面意思理解，既然我們要找一個最大子矩形，那不就是用一根物理上
的懸線，它永遠豎直向下，然后我們可以向左右拓展，直到左邊到底，右邊也到極限為止，
但我們也要注意，懸線拓展出來的不一定是極大子矩形，因為懸線長度不是固定的嗎?所以
我們可以列舉多條懸線嘛，，，
詳細思路：
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);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17900.html
標籤：其他