P5943

_Violet_Evergarden · 2023-08-18 15:09:10 · 题解

来一发双倍经验

题意：

只需找出矩阵中最大的由 0 构成的子矩阵。

思路：

我们只需要记录每个点左边有多少个连续的 0，然后在每个点遍历的时候加上最优性剪枝即可。见代码便可懂。

优化：

目前我们的时间复杂度还是超时的。那我们就用悬线法优化一下，悬线法就是我们对每个点从上往下遍历，用提前储存的左边有多少个 0 来进行计算，最后再加上最优性的遍历即可。此时我们的的时间复杂度就无限趋近 \mathcal{O}(N^2) 就可以拿下了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[2001][2001];
int b[2001][2001];
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        int m=0;
        for(int j=1;j<=n;j++){
            if(a[i][j]==0){
                m++;

            }
            else{
                m=0;
            }
            b[i][j]=m;//存左边有多少个连续的零 
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int p=b[i][j];
            if(p==0){
                continue;
            }
            ans=max(p,ans);
            for(int k=i+1;k<=n;k++){
                p=min(p,b[k][j]);
                if(p==0||p*(n-i+1)<=ans){//最优性剪枝 
                    break;
                }
                ans=max(p*(k-i+1),ans);
            }
        }
    }
    cout<<ans;
    return 0;
}