【BZOJ】3039: 玉蟾宫 悬线法

【题意】给定01矩阵，求最大全1子矩阵。n,m<=1000。

【算法】动态规划（悬线法）

【题解】★对于01矩阵中的任意一个全1极大子矩阵，都可以在其上边界遇到的障碍点处悬线到下边界的点x，则点x唯一对应了一个极大子矩阵，那么至多有n*m个极大子矩阵，而最大子矩阵一定是极大子矩阵，故求解复杂度O(nm)。

预处理L[i][j]表示(i,j)向左延伸的最左位置，R[i][j]同理。

设h[i][j]表示(i,j)向上的悬线高度，l[i][j]表示(i,j)代表的极大子矩阵向左延伸的最左位置，r[i][j]同理。

a[i][j]=1，则有：h[i][j]=h[i-1][j]　　l[i][j]=max{ l[i-1][j] , L[i][j]}　　r[i][j]=min{ r[i-1][j] , R[i][j] }

注意初始化r[0][i]=m+1。

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int n,m,a[maxn][maxn],L[maxn][maxn],R[maxn][maxn],l[maxn][maxn],r[maxn][maxn],h[maxn][maxn],ans=;

char s[];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            scanf("%s",s);

            if(s[]=='F')a[i][j]=;else a[i][j]=;

        }

    }

    for(int i=;i<=n;i++){

        int left=,right=m+;

        for(int j=;j<=m;j++)if(a[i][j])L[i][j]=left;else left=j;

        for(int j=m;j>=;j--)if(a[i][j])R[i][j]=right;else right=j;

    }

    for(int i=;i<=m;i++)r[][i]=m+;

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(a[i][j]){

                h[i][j]=h[i-][j]+;

                l[i][j]=max(l[i-][j],L[i][j]);

                r[i][j]=min(r[i-][j],R[i][j]);

            }

            else h[i][j]=,l[i][j]=,r[i][j]=m+;

            ans=max(ans,h[i][j]*(r[i][j]-l[i][j]-));

        }

    }

    printf("%d",ans*);

    return ;

}

图大点稀的情况可以用另一种方法寻找极大子矩阵：从左到右枚举障碍点，考虑向右扩展障碍点并压缩矩阵大小（左边界必须包含原障碍点），复杂度O(S^2)，这是基于极大子矩阵一定四个边界都被障碍点卡住的思想。注意在左右边界遍布障碍点。