P5943 [POI2002] 最大的园地

xh001 · 2023-08-18 14:58:41 · 题解

题意

首先给定一个整数 n 表示正方形的边长，然后读入一个 n\times n 的由 0、1 构成的矩阵，求最大的由 0 构成的子矩阵的面积。

思路

先 \mathcal{O}(n^2) 的预处理出点 (i,j) 左边（包括自己）有多少个连续的 0，然后暴力枚举每个点并记录当前子矩阵的横向长度，在每个点的基础上继续向下枚举，每次取最小的横向长度并乘上竖直长度。但是，很显然这样会超时，所以开始优化。

优化1

当当前横向长度为 0 时，直接枚举下一个点。

证明：很显然，面积为 0 的子矩阵不会对答案有任何贡献。

优化2（重点）

当当前横向长度乘上竖直长度后仍小于等于 ans 时，直接枚举下一个点。

证明：再往下遍历只会让横向长度单调不上升，当前子矩阵面积不可能更大。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//好习惯。 
ll n,m,a[2001][2001],cnt,ans;
ll f[2001][2001];//记录点(i,j)左边（包括自己）有多少个连续的0。 
ll s;//当前子矩阵横向长度。 
inline ll read()
{
    ll k=0,f=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) f|=c=='-';
    for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
    return f?-k:k;
}
int main()
{
    n=read();
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            a[i][j]=read();
        }
    }
    for(ll i=1;i<=n;i++)
    {
        cnt=0;
        for(ll j=1;j<=n;j++)
        {
            if(!a[i][j]) cnt++;
            else cnt=0;
            f[i][j]=cnt;
        }
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            s=f[i][j];
            ans=max(ans,s);
            for(ll l=i+1;l<=n;l++)
            {
                s=min(s,f[l][j]);
                if(!s) break;//优化1。 
                if(s*(n-i+1)<=ans) break;//优化2。 
                ans=max(ans,s*(l-i+1));
            }
        }
    }
    cout<<ans;
    return 0;
}