下午看了03年的论文，学了一下悬线法，不过好像针对这种问这种最大子矩形的题，还有另外一种算法（跟障碍点的数目有关），悬线法是跟（地图的大小有关）。针对这道题还有一种神奇的dp写法。
论文： 浅谈用极大化思想解决最大子矩形问题_百度文库
http://wenku.baidu.com/view/728cd5126edb6f1aff001fbb.html
加油了。
这是悬线法写的
1 #include<cstdio> 2 #include<iostream> 3 #define rep(i,j,k) for(int i = j; i <= k; i++) 4 #define down(i,j,k) for(int i = j; i >= k; i--) 5 #define maxn 1005 6 using namespace std; 7 8 int a[maxn][maxn], h[maxn][maxn], l[maxn][maxn], r[maxn][maxn]; 9 10 int read() 11 { 12 int s = 0, t =1; char c = getchar(); 13 while(!isdigit(c) ){ 14 if( c == ‘-‘ ) t = -1; c =getchar(); 15 } 16 while( isdigit(c) ){ 17 s = s * 10+ c - ‘0‘; c =getchar(); 18 } 19 return s * t; 20 } 21 22 int main() 23 { 24 int n = read(), m = read(), ans = 0; 25 rep(i,1,n){ 26 rep(j,1,m) a[i][j] = read(); 27 } 28 rep(i,1,m) l[0][i] = 1, r[0][i] = m; 29 rep(i,1,n){ 30 rep(j,1,m){ 31 if( !a[i][j] ){ 32 h[i][j] = 0; l[i][j] = 1; r[i][j] = m; 33 } 34 else { 35 h[i][j] = h[i-1][j]+1; 36 l[i][j] = l[i-1][j], r[i][j] = r[i-1][j]; 37 down(k,j-1,l[i-1][j]) if( !a[i][k] ) { 38 l[i][j] = k+1; 39 break; 40 } 41 rep(k,j+1,r[i-1][j]) if( !a[i][k] ){ 42 r[i][j] = k-1; 43 break; 44 } 45 ans = max(ans,min((r[i][j]-l[i][j]+1),h[i][j])); 46 } 47 } 48 } 49 cout<<ans<<endl; 50 return 0; 51 }
这是dp写的，用f[i][j]表示以 第 i 行第 j 列作为右下角方块的最大正方形边长。 那么状态转移方程就是 f[i][j] = min( f[i-1][j], f[i-1][j-1], f[i][j-1] ) + 1;
正确性应该不难证吧！
1 #include<stdio.h> 2 #include<string.h> 3 int f[1005][1005]; 4 int a[1005][1005]; 5 int min(int a,int b) 6 { 7 if(a>b) return b; 8 else return a; 9 } 10 int main() 11 { 12 memset(f,0,sizeof(f)); 13 int n,m,max=-1; 14 scanf("%d%d",&n,&m); 15 for(int i=1;i<=n;i++) 16 for(int j=1;j<=m;j++) 17 scanf("%d",&a[i][j]); 18 for(int i=1;i<=n;i++) 19 for(int j=1;j<=m;j++) 20 { 21 if(a[i][j]==1) 22 f[i][j]=min(min(f[i-1][j],f[i-1][j-1]),f[i][j-1])+1; 23 if(f[i][j]>max) max=f[i][j]; 24 } 25 printf("%d\n",max); 26 return 0; 27 }
原文：http://www.cnblogs.com/83131yyl/p/5093677.html