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

思路：

状态压缩不懂看，http://blog.csdn.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;

}