【BZOJ】3039: 玉蟾宫悬线法

傷城~ 2022-01-07 01:53 131阅读 0赞

【题意】给定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。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=1010;
    int n,m,a[maxn][maxn],L[maxn][maxn],R[maxn][maxn],l[maxn][maxn],r[maxn][maxn],h[maxn][maxn],ans=0;
    char s[10];
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%s",s);
                if(s[0]=='F')a[i][j]=1;else a[i][j]=0;
            }
        }
        for(int i=1;i<=n;i++){
            int left=0,right=m+1;
            for(int j=1;j<=m;j++)if(a[i][j])L[i][j]=left;else left=j;
            for(int j=m;j>=1;j--)if(a[i][j])R[i][j]=right;else right=j;
        }
        for(int i=1;i<=m;i++)r[0][i]=m+1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]){
                    h[i][j]=h[i-1][j]+1;
                    l[i][j]=max(l[i-1][j],L[i][j]);
                    r[i][j]=min(r[i-1][j],R[i][j]);
                }
                else h[i][j]=0,l[i][j]=0,r[i][j]=m+1;
                ans=max(ans,h[i][j]*(r[i][j]-l[i][j]-1));
            }
        }
        printf("%d",ans*3);
        return 0;
    }

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

转载于:https://www.cnblogs.com/onioncyc/p/8311011.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/7bf012b0aa734663be5adbc967491663.png