poj 3254 Corn Fields
题目解释：给你一个n*m的草地1为肥沃，0为贫瘠，现在放牛在肥沃土地上，牛不能相邻，问有多少种放法
用dp[i][j]表示第i行，状态为j的方案数
用位运算巧妙处理那些状态
0.用二进制数表示每一行草地的状态s[i]
1.枚举的状态符合草地的肥沃块：s[i]|k==s[i]
2.枚举的上一行状态k 不能出现连续的1：k&(k<<1)==0
3.上下两行不存在相邻的1：j&k==0
又写了一遍这个题，发现坑点主要是那几个括号，位运算和==，!=使用不加括号会死的
比如35行39行
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<bitset> 7 #define llint long long 8 #define re register 9 #define De(a) cout<<a<<endl 10 #define pau system("pause") 11 #define wline putchar('\n') 12 using namespace std; 13 const llint mod = 100000000; 14 int n,m; 15 llint dp[13][1<<12]; 16 int s[13]; 17 int a; 18 int main() 19 { 20 scanf("%d%d",&n,&m); 21 for(int i=1;i<=n;i++) 22 { 23 for(int j=0;j<m;j++) 24 { 25 scanf("%d",&a); 26 s[i]=(s[i]<<1)+a; 27 } 28 } 29 dp[0][0]=1;//初始化，什么也不放的状态 30 for(int i=1;i<=n;i++) //枚举行 31 { 32 for(int j=0;j<(1<<m);j++) //枚举当前行的状态 33 { 34 if((j<<1)&j||(j>>1)&j) continue; //剪枝：该状态不存在相邻的1 35 if((j&s[i]) != j) continue; //保证在肥沃土地上放牛 36 for(int k=0;k<(1<<m);k++) 37 { 38 if((k<<1)&k||(k>>1)&k) continue; 39 if((j&k)==0)//符合草地的状态，且满足上下两行没有相邻的1 40 { 41 dp[i][j]= (dp[i][j] + dp[i-1][k])%mod; 42 } 43 } 44 } 45 } 46 llint ans=0; 47 for(int i=0;i<(1<<m);i++) ans = (ans + dp[n][i])%mod; 48 printf("%lld",ans); 49 }
