POJ 3254 Corn Fields：网格密铺类状压dp

题目链接：http://poj.org/problem?id=3254

题意：

　　给你一片n*m的耕地，你可以在上面种玉米。但是其中有一些地方是荒芜的，不能种植。并且种植玉米的地方不能相邻。问你在这片地上有多少种种植方案。

题解：

　　思路：一行一行种

　　状态表示：

　　　　dp[state][i] = num of ways at ith row

　　　　（1）当前种到了第i行

　　　　（2）第i行有哪些地方种了玉米，状态为state

　　如何转移：

　　　　约束条件：

　　　　　　（1）对于当前行，已经在某些地方种过了玉米，那么在下一行的对应位置就不能再种。

　　　　　　（2）在每一行内部，种植玉米不能相邻。

　　　　　　所以可以预处理（dfs）出在一行上每一种state对应的下一行可以种的方案nex。

　　　　转移条件：

　　　　　　（1）state在当前第i行合法。

　　　　　　（2）state对应的nex在i+1行合法。

　　　　　　所以在读入的时候，就可以预处理出每一行土地的情况field[i]。二进制下每一位0代表可以种，1代表不能种。

　　　　　　以上两个条件就变成了：(state&field[i])==0 和 (nex&field[i+1])==0

　　　　转移：

　　　　　　三重for循环，枚举种到第i行、当前行的种植方案state、state对应的下一行的种植方案nex。

　　　　　　dp[state|nex][i+1] += dp[state][i]

AC Code：

 1 // optimizations:
 2 // 1) a state is legal at a row only if: state&field == 0
 3 // 2) preprocess the states can be transfered from another state
 4 
 5 #include <iostream>
 6 #include <stdio.h>
 7 #include <string.h>
 8 #include <vector>
 9 #define MAX_N 15
10 #define MAX_S (1<<14)
11 #define MOD 100000000
12 
13 using namespace std;
14 
15 int n,m;
16 int ans;
17 int field[MAX_N];
18 int dp[MAX_S][MAX_N];
19 vector<int> transfer[MAX_S];
20 
21 void read()
22 {
23     memset(field,0,sizeof(field));
24     cin>>n>>m;
25     int temp;
26     for(int i=0;i<n;i++)
27     {
28         for(int j=0;j<m;j++)
29         {
30             cin>>temp;
31             field[i]<<=1;
32             field[i]|=(!temp);
33         }
34     }
35     field[n]=(1<<m)-1;
36 }
37 
38 void dfs(int col,int state,int nex)
39 {
40     if(col>=m)
41     {
42         transfer[state].push_back(nex);
43         return;
44     }
45     if(!((state>>col)&1)) dfs(col+2,state,nex|(1<<col));
46     dfs(col+1,state,nex);
47 }
48 
49 void solve()
50 {
51     for(int state=0;state<(1<<m);state++)
52     {
53         dfs(0,state,0);
54     }
55     memset(dp,0,sizeof(dp));
56     for(int i=0;i<transfer[0].size();i++)
57     {
58         int state=transfer[0][i];
59         if(!(field[0]&state)) dp[state][0]=1;
60     }
61     for(int i=0;i<n;i++)
62     {
63         for(int state=0;state<(1<<m);state++)
64         {
65             if(dp[state][i]!=0 && !(field[i]&state))
66             {
67                 for(int j=0;j<transfer[state].size();j++)
68                 {
69                     int nex=transfer[state][j];
70                     if(!(field[i+1]&nex))
71                     {
72                         dp[nex][i+1]+=dp[state][i];
73                         dp[nex][i+1]%=MOD;
74                     }
75                 }
76             }
77         }
78     }
79 }
80 
81 void print()
82 {
83     cout<<dp[0][n]<<endl;
84 }
85 
86 int main()
87 {
88     read();
89     solve();
90     print();
91 }

POJ 3254 Corn Fields：网格密铺类 状压dp

POJ 3254 Corn Fields：网格密铺类状压dp