ZOJ 2563 Long Dominoes（状态压缩DP）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1563

题目大意：在h*w的矩阵里铺满1*3的小矩阵，共有多少种方法

Sample Input

3 3
3 10
0 0

Sample Output

2
28

分析：状态压缩DP，跟ZOJ 1100 及其相识，不过那道题目使用1*2的木板平铺，题解链接：http://www.cnblogs.com/acm-bingzi/p/3289994.html

　　但是不能照搬这道题目的方法，3^9约等于20000，两次循环的话会超时，所以每次只找符合条件的状态。

　　每个格子有三种状态0,1,2， 0----横放或者竖放的第三个格子对下层没有影响，1----竖放的中间那个格子对下一层有影响，2----竖放的第一个格子对下两层有影响。

　　dp[i][j]表示到第i层状态为j的方法数。

代码如下：

 1 # include<stdio.h>
 2 # include<string.h>
 3 # include<math.h>
 4 # define LL long long
 5 LL dp[31][20000];
 6 int h,w;    //高度、宽度
 7 int zt,row; //状态、行数
 8 int pos[10],dig[10];
 9 void init()
10 {
11     pos[0] = 1;
12     for(int i=1; i<=9; i++)
13         pos[i] = pos[i-1]*3;
14 }
15 
16 void get()  //得到该状态3进制下的各个位上的数字
17 {
18     int s=zt,len = 0;
19     memset(dig,0,sizeof(dig));
20     while(s)
21     {
22         dig[len++] = s%3;
23         s = s/3;
24     }
25 }
26 
27 void dfs(int col,int s)     //这一行状态s受zt的影响，col表示列，作为标记
28 {
29     if(col==w)  //当到达最大宽度时，需要运算
30     {
31         dp[row][s] += dp[row-1][zt];
32         return;
33     }
34     if(dig[col]==0) //上一层是0
35     {
36         if(col+2<w && dig[col+1]==0 && dig[col+2]==0)   //横着放，下一层为0
37             dfs(col+3,s);
38         dfs(col+1,s+2*pos[col]);    //竖着放，下一次为2
39     }
40     else if(dig[col]==1)    //上一层为1时下一层只能为0
41         dfs(col+1,s);
42     else
43         dfs(col+1,s+pos[col]);  //上一层为2时下一层只能为1
44 }
45 
46 int main()
47 {
48     init();
49     while(scanf("%d%d",&w,&h),h+w)
50     {
51         if((h*w)%3)         //这种情况下无论如何也不能填满
52         {
53             printf("0
");
54             continue;
55         }
56         memset(dp,0,sizeof(dp));
57         dp[0][0] = 1;
58         for(row=1; row<=h; row++)
59             for(zt=0; zt<pos[w]; zt++)
60             {
61                 if(dp[row-1][zt])
62                 {
63                     get();
64                     dfs(0,0);
65                 }
66             }
67         printf("%lld
",dp[h][0]);
68     }
69     return 0;
70 }