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]++;elseh[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; }

總結

以上是生活随笔為你收集整理的最大0，1子矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。