无

1.codevs1159

题目描述 Description

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

思路:神奇。预处理当前点向上有几个零，当前点到达的左边界，右边界，更新左右边界扩展矩形，计算答案

详见 http://www.cnblogs.com/L-Memory/p/7354043.html

#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;   
}