http://poj.org/problem?id=3254
题意：给出一个n行m列的草地，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。
分析：假如我们知道第 i-1 行的所有的可以放的情况，那么对于第 i 行的可以放的一种情况，我们只要判断它和 i - 1 行的所有情况的能不能满足题目的所有牛不相邻，如果有种中满足，那么对于 i 行的这一中情况有 x 中放法。
前面分析可知满足子状态，我们我们确定可以用dp来解决。
但是我们又发现，状态是一种放法，不是我们平常dp的简单的状态，所以要用状态压缩！
但是什么是状态压缩呢?
比如前面的情况，一种放法是最多由12个 0 或者 1 组成的，那么我们很容易想到用二进制，用二进制的一个数来表示一种放法。
定义状态dp【i】【j】，第 i 行状态为 j 的时候放牛的种数。j 的话我们转化成二进制，从低位到高位依次 1 表示放牛0表示没有放牛，就可以表示一行所有的情况。
那么转移方程 dp【i】【j】=sum（dp【i-1】【k】）
状态压缩dp关键是处理好位运算。
这个题目用到了 & 这个运算符。
用 x & （x<<1）来判断一个数相邻两位是不是同时为1，假如同时为 1 则返回一个值，否则返回 0 ，这样就能优化掉一些状态
用 x & y 的布尔值来判断相同为是不是同时为1。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 typedef long long LL; 6 const int mod = 1e8; 7 const int N = 13; 8 const int M = 1 << N; 9 int dp[N][M], map[N], res[M]; 10 int judge1(int x) 11 { 12 return (x & (x << 1)); 13 } 14 int judge2(int i, int j) 15 { 16 return (map[i] & res[j]); 17 } 18 int main() 19 { 20 int n, m; 21 scanf("%d %d", &n, &m); 22 int temp; 23 for(int i = 1; i <= n; i++) 24 for(int j = 1; j <= m; j++) 25 { 26 scanf("%d", &temp); 27 if(temp == 0) 28 map[i] += (1 << (j - 1));//注意不肥沃为1,这里很巧妙 29 } 30 int k = 0; 31 for(int i = 0; i < (1 << m); i++) 32 if(judge1(i) == 0) 33 res[k++] = i; 34 for(int i = 0; i < k; i++) 35 { 36 if(!judge2(1, i))//如果在不肥沃的地方放牛(相与为1时)，就不保存 37 dp[1][i] = 1; 38 } 39 for(int i = 2; i <= n; i++) 40 { 41 for(int j = 0; j < k; j++) 42 { 43 if(judge2(i, j)) 44 continue; 45 for(int f = 0; f < k; f++) 46 { 47 if(judge2(i - 1, f)) 48 continue; 49 if(!(res[j] & res[f])) 50 dp[i][j] += dp[i - 1][f];//dp[i][0]保存了前面几行的所有状态 51 } 52 } 53 } 54 LL sum = 0; 55 for(int j = 0; j < k; j++){ 56 sum = (sum + dp[n][j]) % mod; 57 } 58 printf("%lld ", sum); 59 return 0; 60 }