POJ 2411 Mondriaans Dream

題意：在n ,m 大的格子上鋪滿1*2的方格，問最多有多少種鋪法

一道經典的輪廓線dp，白書上有解析，這裡具體分析一下整個過程

下面使用滾動數組，內存的利用率是非常高的

dp過程是對[i , j] 點的不斷更新，使dp[ i, j ]是此點的最優解，很顯然子問題的最優解是原問題的必要條件，因此遍歷 [ i , j ]得到的dp[i,j] 都是最優解

// 使用dp的條件 ：子問題最優可推出上一層遞歸問題最優

dp[i , j] 表示 第i行的j狀態下 最多鋪法

先看一下狀態轉移過程：

對於[i,j]點，狀態轉移共有三種：

[i,j]點不放

1、[i,j]點不放時，K9點必須放，不然鋪不滿，所以只有當K9=1時，轉移到二進制為 K8K7K6...K2K1K00這個狀態 0就是[i,j]點

[i,j]點放     (我們只需要考慮往上放和往左放，因為現在是求最優解，如此考慮即可)

2、往上放 必須 K9=0 , 轉移到 K8K7K6...K1K0 1

3、往左放 ,  此時必須 K0= 0  &&  K9=1 （表示K9已經放過了，這樣才能鋪滿） 轉移到 K8K7K6...K1 1 1

幾個細節：

1. 所謂的狀態轉移，在上述中就是 加法

2. 下面第三重for中 k值遍歷的是  以K0為終點的所有狀態，而不是以 [i,j]點為終點的狀態

3. 恰如2，轉移到的狀態（藍色字體）就是以 [i,j] 點為終點的狀態

4.程序中的操作其實是：把[i,j-1] 這個點的所有狀態轉移給 [i,j]   , 抓住這句就能很快理解代碼了

1、遍歷 [i,j]點

for(i -> n)

for(j-> m)

for( k =0-> (1<<m)-1)// 遍歷[i,j]前面點的狀態

k就表示 [i,j] 點前面格子的狀態，就是上圖綠色格子的狀態，k用2進制表示，0表示不放，1表示放了

k= K9 K8 K7 K6 K5...

2、根據上述3個狀態把[i,j-1] 點的所有狀態都轉移給 [i,j] 點

3、 根據dp數組含義，結論應該是 dp[ n-1 ][ (1<<m)-1]  ，這裡使用滾動數組所以答案是 dp[cur][ (1<<m)-1] // cur 表示當前行

 #include<stdio.h>   
#include<string.h>   
#define N 12   
#define ll long long   
ll dp[2][1<<N],n,m,cur;  
void updata(ll a,ll b){  
    if(b & 1<<m )dp[cur][b^(1<<m)] += dp[1-cur][a];  
}  
int main()  
{  
    ll i,j,k;  
    while(scanf("%lld %lld",&n,&m),n){  
        if(n<m){i=n;n=m;m=i;}  
        memset(dp,0,sizeof(dp));  
        dp[0][(1<<m)-1]=1;  
        cur=0;  
        for(i=0;i<n;i++)  
            for(j=0;j<m;j++){  
                cur^=1;  
                memset(dp[cur],0,sizeof(dp[cur]));  
                for(k=0;k<(1<<m);k++){  
                    updata(k,k<<1);  
                    if( i && !(k & (1<<m-1))) updata(k, (k<<1)^(1<<m) ^1);  
                    if( j && !(k & 1)) updata(k, (k<<1)^3);//把 二進制（k 0）的最後2位變成 1   
                }  
            }  
            printf("%lld\n",dp[cur][(1<<m)-1]);  
    }  
    return 0;  
}