poj 2411 Mondriaan's Dream_状态压缩dp

题意：给我们1*2的骨牌，问我们一个n*m的棋盘有多少种放满的方案。

思路：

状态压缩不懂看，http://blog.****.net/neng18/article/details/18425765

用1表示放置了骨牌，0表示没有放置。dp[i][j]表示第i行为状态j是有多少种方案。

分下面3种情况进行转移： d表示当前列号，s1 表示本行的状态，s2表示上一行的状态，

1 竖直放置   那么d=d+1，s1<<1|1 , s2<<1;

这是什么意思呢？ 这表示上一行在d列没有放置骨牌，那么这一行必须放置。下面同理。

2 水平放置 那么 d=d+2,s1<<2|3,s2<<2|3;

3 不放置   那么 d=d+1,s1<<1,s2<<1|1;

初始化 d=1，s1=s2=0; 第一行放置时，可以虚拟第0行，看做已经放好了。那么他的情况就只有两种,见init（）。

注意用大整型。

#include<iostream>
#include<algorithm>
const int N = 12;
const int maxn = 1<<N;
using namespace std;
int n,m;
__int64 dp[N][maxn];
void init(int d,int s)//初始化第一行
{
     if(d == m+1)
     {
        dp[1][s]++;
         return;
     }
     if(d + 1 <= m+1)
         init(d+1,s<<1);//竖放
     if(d + 2 <= m+1)
         init(d+2,s<<2|3);//平放
}
void dfs(int d,int s1,int s2,int row)//d对应当前列号，s1对应本行，s2对应上的状态,row为当前行号
{
     if(d == m+1)
     {    dp[row][s1]+=dp[row-1][s2]; return ; }
     if(d + 1 <= m+1)
     {
          dfs(d+1,s1<<1|1,s2<<1,row);//竖放
          dfs(d+1,s1<<1,s2<<1|1,row);//不放
     }
     if(d + 2 <= m+1)
          dfs(d+2,s1<<2|3,s2<<2|3,row);//平放
}
int main()
{

    while(scanf("%d%d",&n,&m)!=EOF && (m || n))
    {
         if((m*n)%2) { puts("0"); continue; }//都为奇数时候放不下。
         memset(dp,0,sizeof(dp));
         init(1,0);
         for(int i=2;i<=n;i++)
            dfs(1,0,0,i);
         printf("%I64d\n",dp[n][(1<<m)-1]);
    }
    return 0;
}