1159 最大全0子矩阵(预处理)

1159 最大全0子矩阵

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 

 

 

题目描述 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

思路转自 http://blog.csdn.net/qq_35264769/article/details/53066287

这个题可以预处理矩阵前缀和然后用n^3的方法解决，可是明显会超时，所以有一种n^2的算法。 
我们可以一行一行的去算，设h[j]为从当前行开始向上数连续的0的个数（当前第i行也为0），如果当前位置等于1的话那么h[j]=0。 
比如说样例：

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 
那么每个位置的h[j]为 
1 0 1 0 1 
2 1 2 1 2 
3 2 2 2 0 
0 3 4 3 1 
1 0 5 4 2 
然后我们在求出来每一行h[j]的同时，去找当前位置可以到达的左边界和右边界。我们设l[j]，r[j]为左右边界。我们设l[j],r[j]初始值都为j。显然，如果h[j]<=h[l[j]-1],那么l[j]=l[l[j]-1]；对应着，如果h[j]<=h[r[j]+1],那么r[j]=r[r[j]+1]; 
我们来举个例子； 
 
 
 
 
 
还有一个要注意的问题，因为到每一行的时候，h[j]都会跟着更新，所以我们每次求出来h[j]的时候应该紧跟着去求他的l和r，并且算面积。

#include<iostream>
#include<cstdio>
#include<cstring>

#define N 2007

using namespace std;
int map[N][N],h[N],l[N],r[N],ans;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        scanf("%d",&map[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(map[i][j]==0) h[j]++;
            else h[j]=0;
        }
        for(int j=1;j<=n;j++)
        {
            l[j]=j;
            while(l[j]>1 && h[j]<=h[l[j]-1])
              l[j]=l[l[j]-1];
        }
        for(int j=n;j>=1;j--)
        {
            r[j]=j;
            while(r[j]<n && h[j]<=h[r[j]+1])
              r[j]=r[r[j]+1];
        }
        for(int j=1;j<=n;j++)
           ans=max(h[j]*(r[j]-l[j]+1),ans);        
    }
    printf("%d
",ans);
    return 0;   
}