http://www.cppblog.com/RyanWang/archive/2009/08/13/93129.html
描述
在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多
输入
单组数据第一行为整数N,其中1<=N<=2000,为方阵的大小,紧接着N行每行均有N个0或1,相邻两数间严格用一个空格隔开
输出
输出仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数
样例输入
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
样例输出
9
这题只能用O(n^2)的方法,O(n^3)的dp会超时。
这时可以一行一行地推,设置一个h[i]代表从第一行到当前行,第i列的连续0的个数(当前行第i列为0)。设置l[],r[]数组代表某行高度为>=h的左右边界。
则对于
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[]为别为
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[]值可以更新左右边界l[],r[]
初始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[]和l,r边界可以计算出从以第i行为结尾的最大面积Si=h[j]*(r[j]-l[j]+1)|1<=j<=n
最后,取这个面积的最大值。
#include<iostream> using namespace std; int f[2001][2001]; int h[2001],l[2001],r[2001]; int n,i,j; int main() { scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&f[i][j]); } } int ma=0; for(i=1;i<=n;i++)//一行一行处理,h[j]存储的是到第i行时,在第j列从i行开始往上的0的个数 { for(j=1;j<=n;j++) { if(f[i][j]==0) h[j]++; else h[j]=0; } for(j=1;j<=n;j++)//l[]上一行的结果不影响这一行的 { l[j]=j;//先假设第i行的第j个元素的左边界为j; while(l[j]>1&&h[j]<=h[l[j]-1])//将左边界向左扩展,但是要保持要扩展的边界l[j]-1的高度要大于等于j的高度 l[j]=l[l[j]-1]; } for(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(j=1;j<=n;j++) { if(ma<h[j]*(r[j]-l[j]+1)) ma=h[j]*(r[j]-l[j]+1); } } printf("%d\n",ma); return 0; }