【codevs 1159】最大全0子矩阵（悬线法）-白红宇

【codevs 1159】最大全0子矩阵（悬线法）

阅读量：5287 次

发布时间：2019-06-14

本文共 1333 字，大约阅读时间需要 4 分钟。

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

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

【最大子矩阵的第二种算法模板】

#include
    
     #include
     
      #include
      
       using namespace std;int h[2010][2010],l[2010][2010],r[2010][2010];int n,maxl,maxr,ans,a[2010][2010];int main(){    int i,j;    scanf("%d",&n);    for(i=1;i<=n;++i)     for(j=1;j<=n;++j)      scanf("%d",&a[i][j]);    for(i=1;i<=n;++i) r[0][i]=n;    for(i=1;i<=n;++i)     {
            maxr=n; maxl=1;        for(j=1;j<=n;++j)          if(a[i][j])           {
                maxl=j+1;            h[i][j]=l[i][j]=0;            }           else             {
                    h[i][j]=h[i-1][j]+1;                l[i][j]=max(maxl,l[i-1][j]);            }        for(j=n;j>0;--j)         if(a[i][j])          {
                maxr=j-1;            r[i][j]=n;          }         else          {
                r[i][j]=min(maxr,r[i-1][j]);            ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);          }      }     printf("%d",ans);    return 0;}