Code[VS]1159 最大全0子矩阵

原题链接：http://codevs.cn/problem/1159/

题目描述 Description

在一个0,1方阵中找出其中最大的全0子矩阵，所谓最大是指O的个数最多。

输入描述 Input Description

输入文件第一行为整数N，其中1<=N<=2000，为方阵的大小，紧接着N行每行均有N个0或1，相邻两数间严格用一个空格隔开。

输出描述 Output Description

输出文件仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数。

样例输入 Sample Input

5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0

样例输出 Sample Output

9

题解

悬线法模板题。

对于每个点，我们维护一下该点向上最大能扩展多少，以及这个点的悬线向左向右能平移多少，然后枚举所有悬线求最大子矩形即可，复杂度O(nm)$O(nm)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int M=2e3+5;
int n,h[M][M],l[M][M],r[M][M],sq[M][M];
void in()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    scanf("%d",&sq[i][j]);
}
void ac()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        h[i][j]=sq[i-1][j]?1:h[i-1][j]+1,
        l[i][j]=sq[i][j-1]?1:l[i][j-1]+1;
        for(int j=n;j>=0;--j)
        r[i][j]=sq[i][j+1]?1:r[i][j+1]+1;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    {
        if(sq[i][j]){h[i][j]=l[i][j]=r[i][j]=0;continue;}
        if(i>1&&!sq[i-1][j])
        l[i][j]=min(l[i][j],l[i-1][j]),
        r[i][j]=min(r[i][j],r[i-1][j]);
        ans=max(ans,(l[i][j]+r[i][j]-1)*h[i][j]);
    }
    printf("%d",ans);
}
int main()
{
    in();ac();
    return 0;
}