sgu-250 Constructive Plan

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;
}