状压DP POJ 3254 Corn Fields

  1 /*
  2     状态压缩DP：先处理硬性条件即不能种植的，然后处理左右不相邻的，
  3     接着就是相邻两行查询所有可行的种数并累加
  4 
  5     写错一个地方差错N久:)
  6     详细解释：http://www.tuicool.com/articles/JVzMVj
  7 */
  8 #include <cstdio>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <cmath>
 12 #include <cstring>
 13 #include <string>
 14 #include <map>
 15 #include <set>
 16 using namespace std;
 17 
 18 const int MAXN = 15;
 19 const int INF = 0x3f3f3f3f;
 20 const int MOD = 1e8;
 21 int dp[MAXN][1 << MAXN];
 22 int st[1 << MAXN];
 23 int rem[1 << MAXN];
 24 
 25 int solve(int m)
 26 {
 27     int cnt = 0;
 28     int tot = 1 << m;
 29     for (int i=0; i<tot; ++i)
 30     {
 31         if ((i & (i << 1)) == 0)
 32         {
 33             st[++cnt] = i;
 34         }
 35     }
 36 
 37     return cnt;
 38 }
 39 
 40 void work(int n, int m, int cnt)
 41 {
 42     memset (dp, 0, sizeof (dp));
 43     for (int i=1; i<=cnt; ++i)
 44     {
 45         if ((st[i] & rem[1]) == 0)
 46         {
 47             dp[1][i] = 1;
 48         }
 49     }
 50 
 51     for (int i=2; i<=n; ++i)
 52     {
 53         for (int k=1; k<=cnt; ++k)
 54         {
 55             if ((st[k] & rem[i]) == 0)
 56             {
 57                 for (int j=1; j<=cnt; ++j)
 58                 {
 59                     if (((st[j] & rem[i-1]) == 0) && ((st[j] & st[k]) == 0))
 60                         dp[i][k] = (dp[i][k] + dp[i-1][j]) % MOD;
 61                 }
 62             }
 63         }
 64     }
 65 
 66     int ans = 0;
 67     for (int i=1; i<=cnt; ++i)
 68     {
 69         ans = (ans + dp[n][i]) % MOD;
 70     }
 71 
 72     printf ("%d
", ans);
 73 }
 74 
 75 int main(void)        //POJ 3254 Corn Fields
 76 {
 77     #ifndef ONLINE_JUDGE
 78     freopen ("F.in", "r", stdin);
 79     #endif
 80     
 81     int n, m;
 82     while (~scanf ("%d%d", &n, &m))
 83     {
 84         int cnt = solve (m);
 85 
 86         memset (rem, 0, sizeof (rem));
 87         for (int i=1; i<=n; ++i)
 88         {
 89             int x;
 90             for (int j=1; j<=m; ++j)        //看错n和m
 91             {
 92                 scanf ("%d", &x);
 93                 if (x == 0)
 94                 {
 95                     rem[i] = rem[i] | (1 << (m-j));
 96                 }
 97             }
 98         }
 99 
100         work (n, m, cnt);
101     }
102 
103     return 0;
104 }
编译人生，运行世界！