poj 3254 && 2411

状态压缩dp，感觉还是不清晰，虽说就两种状态 0 1，但是感觉变化太多了，而且状态转移也不好想

题意：给出 N * M的图，上面只有 0 或者 1两种情况，如果是 1 表示这里可以放牛，如果是 0 表示不可以放牛，而且牛是不可以相邻的，问在这片区域内最多有多少种放牛的方案

很简单的一个状态压缩按给出的样例来说

先看第一行（1 表示该位置有牛，0 表示该位置没有牛）可以用二进制串来表示牛的放置情况

0 0 0 （0） 0 0 1（1） 0 1 0 （2） 1 0 0（4） 1 0 1（5）也就是题目中给的第一行最多有这五种情况，分别对应的十进制数为 0 1 2 4 5

第二行

0 0 0 （0） 0 1 0 （2）只有这两种情况，对应的数为 0 2 。当是 0 这种情况时，于第一行的每一种情况都不冲突，所以有 5种，当是第二种情况是，那么与第一行的 2 这种情况有冲突（两头牛不可一相邻）所以是四种情况，所以一共有 9种放牛的方案

所以预处理每一行可以放牛的情况总数，然后计算每一行时判断与上一行是否有冲突

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #define N 100
 7 #define mod 100000000
 8 #define _clr(a,val) (memset(a,val,sizeof(a)))
 9 
10 using namespace std;
11 
12 int n,m;
13 vector<int>num[13];
14 int dp[20][3000]; // dp [i][j] 表示 第 i 行取第 j 种方案时可行的方案数
15 void cal(int x,int y)
16 {
17     for(int i = 0; i < (1 << m); i++)
18     {
19         if((i >> 1) & i || (i << 1) & i) continue; 
20         if(i & y) continue; 
21         num[x].push_back(i);
22     }
23 }
24 int main()
25 {
26     int i,j,k;
27     int x;
28     //freopen("data.txt","r",stdin);
29     while(scanf("%d%d",&n,&m) != EOF)
30     {
31         //_clr(num,0);
32         for(i = 1; i <= n; i++)
33         {
34             num[i].clear();
35             int tem = 0;
36             for(j = 1; j <= m; j++)
37             {
38                 scanf("%d",&x);
39                 x = 1 - x;
40                 tem = tem * 2 + x;
41             }
42             cal(i,tem); // 计算 第 i 行可以放牛的各种情况
43         }
44         _clr(dp,0);
45         for(i = 0; i < num[1].size(); i++)
46         dp[1][i] = 1;
47         for(i = 2; i <= n; i++)
48         {
49             for(j = 0; j < num[i].size(); j++)
50             {
51                 for(k = 0; k < num[i - 1].size(); k++)
52                 {
53                     if(num[i][j] & num[i - 1][k]) // 不为零，说明放牛有冲突，跳过
54                     {
55                         continue;
56                     }
57                     dp[i][j] += dp[i - 1][k];
58                 }
59             }
60         }
61         int ans = 0;
62         for(i = 0; i < num[n].size(); i++)
63         {
64             ans = (ans + dp[n][i]) % mod;
65         }
66         printf("%d\n",ans);
67     }
68     return 0;
69 }

题目：http://poj.org/problem?id=2411

题意：棋盘覆盖问题，给出一个 h * w 的棋盘，让你用 2 * 1的方块或横或竖的去覆盖棋盘，问有多少种方案数

0：表示该格是横放或是由上一层的竖放恰好填上了

1：表示该格竖放并且对下一行有影响

该行的状态可以用一个2进制数来表示，如果是 1，那么下行该格一定为零，但如果为零，那么下行该格可以是 1 也可以是 0

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #define N 20
 7 #define mod 100000000
 8 #define _clr(a,val) (memset(a,val,sizeof(a)))
 9 
10 using namespace std;
11 
12 typedef long long ll;
13 ll dp[N][3000];
14 int h,w;
15 int i,j;
16 void dfs(int x,int s)  // 下层的第 x 个位置，s 为下一层的状态
17 {
18     if(x == w + 1) // 如果 x 是边界时，直接求出下层为状态s 的方案数，返回
19     {
20         dp[i + 1][s] += dp[i][j];
21         return ;
22     }
23     else
24     {
25         if((j >> (x - 1) & 1) == 1)  // 上层为 1，下层为 0
26         dfs(x + 1,s);
27         else  // 上层 为 0
28         {
29             if(x + 1 <= w && (j >> x & 1) == 0) // 下层为 0
30             dfs(x + 2,s);
31             dfs(x + 1,s | (1 << (x - 1))); // 将下层该位置改为 1
32         }
33     }
34 }
35 int main()
36 {
37     //freopen("data.txt","r",stdin);
38     while(scanf("%d%d",&h,&w) != EOF)
39     {
40         if(h == 0 && w == 0) break;
41         if(h * w % 2)
42         {
43             cout<<"0\n";
44             continue;
45         }
46         _clr(dp,0);
47         dp[0][0] = 1;
48         int temp = 1 << w;
49         for(i = 0; i <= h; i++)
50         {
51             for(j = 0; j < temp; j++)
52             {
53                 if(dp[i][j])
54                 dfs(1,0);
55             }
56         }
57         printf("%I64d\n",dp[h][0]);
58     }
59     return 0;
60 }