UVA11270 Tiling Dominoes —— 插头DP

题目链接：https://vjudge.net/problem/UVA-11270

题意：

用2*1的骨牌填满n*m大小的棋盘，问有多少种放置方式。

题解：

骨牌类的插头DP。

1.由于只需要记录轮廓线上m个位置的放置情况（0或1），且m<=10，2^10 = 1024，故可以用二进制对轮廓线的信息进行压缩。

2.二进制中，第0为代表着当前轮廓线位于第0列的位置的放置情况，以此类推。

3.具体情况分析，设当前格子为a[i][j]：

1) 不放置：前提条件为上面的位置a[i-1][j]已经放置了骨牌。原因：如果上面的位置为空，且这次又不放，那么往后就没有机会填补这个空缺了。

2) 往上放：前提条件为上面的位置a[i-1][j]没有放置骨牌。原因显而易见。

3) 往左放：前提条件为上面的位置a[i-1][j]放置了骨牌，且左边的位置a[i][j-1]没有放置骨牌。原因：情况1)和情况2)的综合。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = ;

 int n, m, cur;

 LL dp[][<<MAXN];

 int main()

 {

     while(scanf("%d%d", &n,&m)!=EOF)

     {

         if(n<m) swap(n, m);

         memset(dp, , sizeof(dp));

         cur = ;

         dp[][(<<m)-] = ;    //初始状态，第一个格子的轮廓线上都有插头，所以就防止了往外放

         for(int i = ; i<n; i++)

         for(int j = ; j<m; j++)

         {

             cur ^= ;

             memset(dp[cur], , sizeof(dp[cur]));

             for(int s = ; s<(<<m); s++)   //由于有m个插头，而插头的编号从0开始，故最大状态为(1<<m)-1。

             {

                 //枚举的是上一个格子的所有状态，即当前格子的轮廓线

                 int up = <<j;  //位于第j列的插头，即上插头

                 int left = <<(j-);  //位于第j-1列的插头， 即左插头

                 bool hav_up = s&up;

                 bool hav_left = s&left;

                 if( hav_up )  //不放置，前提是上插头存在

                     dp[cur][s^up] += dp[cur^][s];

                 if( i!= && !hav_up)   //往上边放，前提是上插头不存在

                     dp[cur][s^up] += dp[cur^][s];

                 if( j!= && hav_up && !hav_left ) //往左边放，前提是上插头存在且左插头不存在

                     dp[cur][s^left] += dp[cur^][s];

             }

         }

         printf("%lld\n", dp[cur][(<<m)-]);

     }

 }