题意：

用1*2和2*1的方块将给定长宽的矩形填满。问有多少种放法，对称的算两种。

分析：

状态压缩dp

首先用0表示前一行没有竖块占用这个位置，而1表示该位置和他上方的位置放了一个竖块，从而压缩状态。接下来一行一行的看，每一行都只受上一行的影响，同时影响着下一行的状态，那么如何将现在的状态和下一行的状态联系起来呢？

1. 令dp[i][j]表示第i行状态为j时的方案数，直接把两个状态作为参数进行DFS，在到达每行行尾时更新 dp[i+1][next];。
2. 看poj的discuss中的方法，对于某一行来说，如果横着放了方块后，就将相应的位置置为1，而被上一行占用的位置也已经是1了，那么整行下来，就只有0的位置是要放竖块的了，而此时下一行对应的位置应该为1，可以发现下一行状态就是这一行状态的非！【感觉好巧妙啊！

因为要求正好填满，所以两种方法最后都可以是输出dp[h+1][0]，但是第二种方法也就可以取反直接用dp[h][(1<<w)−1]求。

还有！！位运算注意括号！！

代码：

方法一：

#include<cstdio>

#include<cstring>

const int maxn = 15;

long long dp[maxn][1<<maxn];

int w, h;

void dfs(int a, int b, int now, int next)

{

   if(b == w){

        dp[a+1][next] += dp[a][now];

        return;

   }

   if(now&(1<<b)) dfs(a, b + 1, now, next);

   else {

        dfs(a,  b+1, now, next|1<<b);

        if(b+1< w&&!(now&1<<(b+1)))

             dfs(a, b+2, now,  next);

   }

    return;

}

int main (void)

{

    while(~scanf("%d%d",&h,&w)&&h+w){

        memset(dp, 0, sizeof(dp));

        dp[1][0] = 1;

        dfs(1,0,0,0);

        for(int i = 2; i <= h; i++){

            for(int j = 0; j < 1<<w; j++){

                if(dp[i][j]) dfs(i, 0, j, 0);

            }

        }

        printf("%I64d\n",dp[h+1][0]);

    }

}//266ms

方法二：

#include<cstdio>

#include<cstring>

const int maxn = 15;

long long dp[maxn][1<<maxn];

int w, h;

long long tmp;

void dfs(int a, int b, int now)

{

   if(b == w){

        dp[a][now] += tmp;

        return;

   }

   dfs(a, b + 1,now);//要么被占要么放竖块

   if(b+1<w&&!(now&1<<b)&&!(now&1<<(b+1)))

        dfs(a, b+2, now|(1<<b)|(1<<(b+1)));

    return;

}

int main (void)

{

    while(~scanf("%d%d",&h,&w)&&h+w){

        memset(dp, 0, sizeof(dp));

        tmp = 1;

        dfs(1,0,0);

        for(int i = 2; i <= h; i++){

            for(int j = 0; j < 1<<w; j++){

               if(dp[i-1][j]) {

                    tmp = dp[i-1][j];

                    int next = ~j&((1<<w)-1);

                    dfs(i, 0, next);

                }

            }

        }

        printf("%I64d\n",dp[h][(1<<w)-1]);

    }

}//250MS