最大0，1子矩陣
時間限制(普通/Java):6000MS/20000MS 運行內存限制:65536KByte
總提交:437 測試通過:77
描述
在一個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
最后，取這個面積的最大值。
CODE
#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++)
{
for(j=1;j<=n;j++)
{
if(f[i][j]==0)
h[j]++;
else
h[j]=0;
}
for(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(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;
}