POJ 2411 Mondriaan's 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;  
}

补充：软件开发 , C++ ,