sgu-250 Constructive Plan

题目大意：

给你一个 N?M 的 {0,1} 矩阵，然后只有为 0 的地方可以可用，然后要你找出一个最大的 C ，输出所占大小，并且在原图中把所占的地方改成 8 ，然后输出新的图。
PS:C 的定义就是从上到下三个大小相邻且不为 0 的矩形，左边界需要对齐，并且上面和下面的矩形的右边界都要大于中间的矩形的右边界。

解题思路：

这道题我只想出了 O(N3logN) 的做法，虽然可以过，但是我写到一半写错了，然后偶然间看到了翱?的代码，数了一下发现只有 3 个循环，”卧槽， N3 ，我于是赶快去膜拜了一下”。
O(N3logN) 的算法在这里我就不再赘述了，网上估计可以找得到，我还是讲一下 O(N3) 的算法吧。

First:
我们用 F[i][l][r] 表示以第 i 行，第 l 列和第 l+r?1 列，为下边界的矩形最大的面积。如图：

Second:
然后我们令 G[i][l][r] 表示中间矩形以第 i 行，第 l 列和第 l+r?1 列，为下边界时前两个矩形的最大面积和。如图：

那么显然 G[i][l][r] 转移方程为(当第 i 行第 l 列到第 l+r?1 列都为 0 则为下式，否则为 0 )
G[i][l][r]=max(G[i?1][l][r]+r,r+max(F[i?1][l][k],k>r))
显然 max(F[i?1][l][k],k>r) 可以再循环中用一个变量记录更新以达到 O(1)
Thrid:
令 H[i][l][r] 表示最下面的矩形以第 i 行，第 l 列和第 l+r?1 列，为下边界时的最大答案。如图：

那么同 G 的计算类似， H[i][l][r] 转移方程为(当第 i 行第 l 列到第 l+r?1 列都为 0 则为下式，否则为 0 )
H[i][l][r]=max(H[i?1][l][r]+r,r+max(G[i?1][l][k],k
然后这道题目就解决了。
输出就简单了

说明：本人由于太弱，边看翱?的代码边学的题解，然后一不小心就写得和翱?差不多了 QAQ

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; int n,m; int ch[200][200]={{0}}; short top[200][200][200]={{{0}}}; short F[200][200][200]={{{0}}}; short G[200][200][200]={{{0}}}; short H[200][200][200]={{{0}}}; int area=0; int ai=0,al=0,ar=0; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&ch[i][j]); top[i][j][1]=(short)(ch[i][j]^1)*(top[i-1][j][1]+1); } for(int i=n;i>=1;i--) for(int j=m;j>=1;j--) { if(ch[i][j]==1) continue; for(int k=2;k+j-1<=m && ch[i][k+j-1]==0;k++) { top[i][j][k]=min(top[i][j][1],top[i][j+1][k-1]); F[i][j][k]=top[i][j][k]*k; } } for(int i=2;i<=n;i++) for(int j=m;j>=1;j--) { if(ch[i][j]==1) continue; int k; for(k=1;k+j-1<=m && ch[i][k+j-1]==0;k++);k--; int Max=0; for(int r=m-j+1;r>k;r--) Max=max((int)F[i-1][j][r],Max); for(int r=k;r>=1;r--) { if(G[i-1][j][r]>0) G[i][j][r]=G[i-1][j][r]+r; if(Max>0) G[i][j][r]=max((short)(Max+r),G[i][j][r]); Max=max((int)F[i-1][j][r],Max); } } for(int i=2;i<=n;i++) for(int j=m;j>=1;j--) { if(ch[i][j]==1) continue; int Max=0; for(int k=1;k+j-1<=m && ch[i][k+j-1]==0;k++) { H[i][j][k]=max((H[i-1][j][k]>0)*(H[i-1][j][k]+k),(Max>0)*(Max+k)); Max=max((int)G[i-1][j][k],Max); if(H[i][j][k]>area) { area=H[i][j][k]; ai=i,al=j,ar=k; } } } if(area<5) cout<<-1<
         
          0;ai--) for(int i=1;i<=ar;i++) ch[ai][al+i-1]=8; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%d ",ch[i][j]); puts(""); } } return 0; }