下午看了03年的论文，学了一下悬线法，不过好像针对这种问这种最大子矩形的题，还有另外一种算法（跟障碍点的数目有关），悬线法是跟（地图的大小有关）。针对这道题还有一种神奇的dp写法（针对于题目所问的图形为正方形）。 不过这几种都是n^2的，只不过 采取的方法不同， n也就不同。
论文： 浅谈用极大化思想解决最大子矩形问题_百度文库
http://wenku.baidu.com/view/728cd5126edb6f1aff001fbb.html加油了。
这是悬线法写的
1 #include2 #include 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< <
这是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 #include2 #include 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 }
BZOJ 1057 棋盘制作， 与上面的思想差不多，效率太低了。
吓死我了，我的代码效率太低了，跑了15秒，差点以为要TLE了还好，明早再来改进了。（注意细节，就算样例过了，也要输出中间结果验证一下，WA了一次）
我承认，是我偷懒，写砸了啊！刚刚把 n^3 的复杂度改成 n^2 之后 只跑了3100多毫秒，心好累，要加油啊！ 改成新的代码咯！
1 #include2 #include 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 sqr(x) (x) * (x) 6 #define maxn 2005 7 using namespace std; 8 9 int a[maxn][maxn], l[maxn][maxn], r[maxn][maxn], h[maxn][maxn];10 11 int read()12 {13 int s = 0, t = 1; char c = getchar();14 while( !isdigit(c) ){15 if( c == '-' ) t= -1; c = getchar();16 }17 while( isdigit(c) ){18 s = s * 10 + c - '0'; c = getchar();19 }20 return s * t;21 }22 23 int main()24 {25 int n = read(), m = read(), anszheng = 0, ansju = 0;26 rep(i,1,n){27 rep(j,1,m) a[i][j] = read();28 }29 rep(i,1,m) h[0][i] = 0, l[0][i] = 1, r[0][i] = m;30 rep(i,1,n){31 rep(j,1,m){32 if( a[i][j] == a[i-1][j] && i != 1 ) h[i][j] = 1, l[i][j] = 1, r[i][j] = m;33 else h[i][j] = h[i-1][j] + 1, l[i][j] = l[i-1][j], r[i][j] = r[i-1][j];34 int lbegin = j, rbegin = j;35 if( h[i][j-1] >= h[i][j] && r[i][j-1] >= j ) { //其实改后就多了这一行。36 lbegin = l[i][j-1]; rbegin = r[i][j-1];37 }38 down(k,lbegin,l[i][j]){39 if( a[i][k] == a[i-1][k] && h[i][j] != 1 ) {40 l[i][j] = k + 1; break;41 }42 if( a[i][k] == a[i][k-1] ){43 l[i][j] = k; break;44 }45 }46 rep(k,rbegin,r[i][j]){47 if( a[i][k] == a[i-1][k] && h[i][j] != 1 ) {48 r[i][j] = k - 1; break;49 }50 if( a[i][k] == a[i][k+1] ){51 r[i][j] = k; break;52 }53 }54 ansju = max(ansju,(r[i][j]-l[i][j]+1)*h[i][j]);55 anszheng = max(anszheng,(sqr(min(r[i][j]-l[i][j]+1,h[i][j]))));56 }57 }58 cout< < < <