【POJ3254】Corn Fields（状压DP）

题意：

一个M x N矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，
可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。
问有多少种放牛方案(一头牛都不放也是一种方案)
(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)

思路：状压DP

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<vector>
 7 #include<map>
 8 #include<set>
 9 #define MOD 100000000
10 #define N 12
11 using namespace std;
12 int dp[14][1<<12];
13 int a[14];
14 int b[1<<12];
15 int n,m,x;
16 
17 int main()
18 {
19     freopen("poj3254.in","r",stdin);
20     freopen("poj3254.out","w",stdout);
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=n;i++) a[i]=0;
23     for(int i=1;i<=n;i++)
24      for(int j=1;j<=m;j++) 
25      {
26        scanf("%d",&x);
27        if(x==0) a[i]+=(1<<(j-1)); 
28      }
29     int MAX=(1<<m)-1; 
30     for(int i=0;i<=MAX;i++)
31     {
32         int x=i;
33         b[i]=1;
34         while(x>0)
35         {
36             if((x&1==1)&&((x>>1)&1==1)) {b[i]=0; break;}
37             x>>=1;
38         }
39     }
40     for(int i=0;i<=MAX;i++)
41      if(!(i&a[1])&&(b[i])) dp[1][i]=1;
42     for(int i=2;i<=n;i++)
43      for(int j=0;j<=MAX;j++)
44       if((!(j&a[i]))&&(b[j])) 
45       {
46           dp[i][j]=0;
47           for(int k=0;k<=MAX;k++)
48            if((!(k&a[i-1]))&&(!(j&k))&&(b[k])) dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
49       }
50     int ans=0;
51     for(int i=0;i<=MAX;i++) 
52      if ((!(i&a[n]))&&(b[i])) ans=(ans+dp[n][i])%MOD;
53     printf("%d
",ans);
54     return 0;         
55 }