/*
f(i,j)表示以(i,j)為右下角的最大全0子矩陣的邊長
若a[i][j]==1,f(i,j)=0
否則:f(i,j)=min{ f(i-1,j),f(i,j-1),f(i-1,j-1) }+1
這樣求得的是最大全0正方形子矩陣
要求長方形矩陣,上述思路行不通
假設以(i,j)為右下角的最大矩陣=12
它可能是3*4、4*3、2*6、6*2、1*12、12*1
按上述思路進行狀態轉移的話,取得最優值的方案不唯一時,
所有的方案需要都記下,用於後續的狀態轉移。
在長方形全0子矩陣中,考察某個位置(i,j)
在第i行中,包含(i,j)位置的全0區間長度>=長方形的寬
若第i行是子矩陣的最後一行,由(i,j)位置向上,連續0的個數>=長方形的高
設[l(i,j)..r(i,j)]是第i行上包含(i,j)的全0子區間
第i1行到第i2行且包含(i2,j)的子矩陣需滿足的條件:
(i1..i2,j)均為0,i2-i1+1=矩陣的高
(i,j)對應的區間[l(i,j)..r(i,j)]>=矩陣的寬
孤立地計算l(i,j)、r(i,j),再枚舉i1,i2,j,時間復雜度O(n^3)
l(i,j)與l(i,j-1),r(i,j)與r(i,j+1)之間有關系;
定義h(i,j)表示位置(i,j)向上連續0的個數,h(i,j)與h(i-1,j)之間有關系;
矩形的寬取決於[i1..i2]行中第j列上[l(i,j)..r(i,j)]的最小值
定義l(i,j),r(i,j)分別表示截止到第i行,之前的h(i,j)行中,全0元素的左右區間,
那麼子矩陣的大小=(r(i,j)-l(i,j)+1)*h(i,j)
h(i,j)的遞推關系
if(a[i][j]==0) h(i,j)=h(i,j)+1;
else h(i,j)=0;
l(i,j)的遞推關系
定義mx表示之前0出現的左側位置,初始值=1
if(a[i][j]==0){
l(i,j)=max(l(i-1,j),mx); //mx的值不變
}else{ //a[i][j]===1,此時的h(i,j)=0,不存在包含(i,j)的子矩陣
mx=j+1; l(i,j)=1;
}
r(i,j)的遞推關系
定義mn表示之前0出現的右側位置,初始值=n
if(a[i][j]==0){
r(i,j)=min(mn,r(i-1,j))
}else{
mx=j-1; r(i,j)=n;
}
其中l(i,j),r(i,j),h(i,j)都可以壓縮成一維數組。
*/
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 const int maxn=2010; 5 int n,a[maxn],l[maxn],r[maxn],h[maxn]; 6 int mx,mn,ans; 7 int main() 8 { 9 scanf("%d",&n); 10 for(int col=1;col<=n;col++) 11 l[col]=r[col]=col; 12 for(int row=1;row<=n;row++) 13 { 14 mx=1; mn=n; 15 for(int col=1;col<=n;col++) 16 { 17 scanf("%d",&a[col]); 18 if(a[col]==0) 19 h[col]=h[col]+1; 20 else 21 h[col]=0; 22 if(a[col]==1) 23 mx=col+1; 24 if(a[col]==0) 25 l[col]=max(l[col],mx); 26 else 27 l[col]=1; 28 } 29 for(int col=n;col>0;col--) 30 { 31 if(a[col]==1) 32 mn=col-1; 33 if(a[col]==0) 34 r[col]=min(r[col],mn); 35 else 36 r[col]=n; 37 ans=max(ans,h[col]*(r[col]-l[col]+1)); 38 } 39 } 40 printf("%d\n",ans); 41 return 0; 42 }