HDU 1693 Eat the Trees(插头DP)

USACO 第6章，第一题是一个插头DP，无奈啊。从头看起，看了好久的陈丹琦的论文，表示木看懂。。。

大体知道思路之后，还是无法实现代码。。

此题是插头DP最最简单的一个，在一个n*m的棋盘上，有些点能走，有些点不能走，可以走一条回路，也可以多回路，把所有点走完，有多少种走法。。

这题的背景还是dota，还是屠夫，还是吃树。。。我还是不会玩屠夫啊。。。

学习此题，看的下面的大神的博客，图画很棒，位运算又学了一个新用法。

http://blog.csdn.net/xymscau/article/details/6756351

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define LL __int64
 5 LL dp[12][12][1<<12];
 6 int p[12][12];
 7 int main()
 8 {
 9     int i,j,k,n,m,t,te1,te2,cas = 1;
10     scanf("%d",&t);
11     while(t--)
12     {
13         scanf("%d%d",&n,&m);
14         memset(dp,0,sizeof(dp));
15         for(i = 1;i <= n;i ++)
16         {
17             for(j = 1;j <= m;j ++)
18             {
19                 scanf("%d",&p[i][j]);
20             }
21         }
22         dp[0][m][0] = 1;
23         for(i = 1;i <= n;i ++)
24         {
25             for(j = 0;j < 1<<m;j ++)//换行
26             dp[i][0][j<<1] = dp[i-1][m][j];
27             for(j = 1;j <= m;j ++)
28             {
29                 te1 = 1<<j;
30                 te2 = 1<<(j-1);
31                 for(k = 0;k < 1<<(m+1);k ++)
32                 {
33                     if(p[i][j])//此位置可以走
34                     {
35                         if((k&te1)&&(k&te2))//这个格子有两个插头
36                         dp[i][j][k] = dp[i][j-1][k-te1-te2];
37                         else if((k&te1) == 0&&(k&te2) == 0)//都没有插头
38                         dp[i][j][k] = dp[i][j-1][k|te1|te2];
39                         else
40                         dp[i][j][k] = dp[i][j-1][k] + dp[i][j-1][k^te1^te2];//k^te1^te2表示的在k位和k-1位，变成相反
41                     }
42                     else
43                     {
44                         if((k&te1) == 0&&(k&te2) == 0)
45                         dp[i][j][k] = dp[i][j-1][k];
46                         else
47                         dp[i][j][k] = 0;
48                     }
49                 }
50             }
51         }
52         printf("Case %d: There are %I64d ways to eat the trees.
",cas++,dp[n][m][0]);
53     }
54     return 0;
55 }