poj - 3254 - Corn Fields （状态压缩）超详细
参考了 的博客，在此基础上增加了说明
题意：
农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛。现在输入数据给出这块地的大小及可否放牧的情况，求该农夫有多少种放牧方案可以选择（注意：任何格子都不放也是一种选择，不要忘记考虑！
思路：
在样例中是一个2×3的表格，我们可以用数字的二进制来枚举每一种情况
在样例中第一行是没有障碍物的，全部可以放牛，那么我们可以用二进制表示（1代表放牛，0代表不放牛），如图：| 编号 | 十进制 | |||
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 1 | 0 | 2 |
| 4 | 1 | 0 | 0 | 4 |
| 5 | 1 | 0 | 1 | 5 |
这种用一个数来表示一组数，以降低表示状态所需的维数的解题手段，就叫做状态压缩。
这5个数字的二进制来代表，这就是第一行所有的可能，可以拓展到更多
对于第二行，只有两种| 编号 | 十进制 | |||
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 2 |
当图二是1号情况时，图一可以选择全部，合计5种。
当图二是2号情况时，图一可以选择1，2，4，5号，合计4种，总共9种。那么重点来了
我们用一个连续数组state[i]表示图一图二的情况，也就是
state[1]=0 state[2]=1state[3]=2state[4]=4state[5]=5
1、上限是什么呢，假设有n列，那么上限就是$2^n$，很好理解，每个位置可以放0和1，一共n个位置
2、怎么排除没有用的呢，即障碍物，例如3就不在数组里，我们用与运算（运算规则：0&0=0;0&1=0;1&0=0;1&1=1;），假设当前是数字x，如果（x & x << 1 ）成立，说明相邻两个格子都为1，则该状态不可行现在我们有了可以用来比较的state数组，但是这是建立在没有障碍物的基础上的，我们再去除障碍物影响 首先我们需要记录障碍物位置用数组cur[i]，表示第i行的障碍物（表示方法与上图表示一样）3、去除障碍物影响，枚举state数组，与cur数组进行与运算，（state & cur）如果成立说明有重合，不再进行判断 剩下的工作就是开始计算结果了
状态转移方程
dp[i][k] = $\sum_{j=1}^{n}$dp[i-1][j]
i代表行数，k的大小等于state数组的长度，是一个循环，j与k是一样的
首先计算出第一行的结果，因为第一行只有地形的限制，没有其他行的限制，第一行要单独计算，剩下的是一个暴力循环 具体看代码代码：
#include#include #include using namespace std;#define mod 100000000int M, N, top = 0;//top表示每行最多的状态数int state[600], num[110];//state存放每行所有的可行状态（即没有相邻的状态//int dp[20][600];//dp[i][j]:对于前i行数据，每行有前j种可能状态时的解int cur[20];//cur[i]表示的是第i行整行的情况inline bool ok(int x) { //判断状态x是否可行 if (x & x << 1) return false;//若存在相邻两个格子都为1，则该状态不可行 return true;}void init() { //遍历所有可能的状态 top = 0; int total = 1 << N; //遍历状态的上界 左移运算 for (int i = 0; i < total; ++i) { if (ok(i)) state[++top] = i;//可以排除左右相邻的情况 }}inline bool fit(int x, int k) { //判断状态x 与第k行的实际状态的逆是否有‘重合’ if (x & cur[k])return false; //若有重合，（即x不符合要求） return true; //若没有，则可行}int main() { while (scanf("%d%d", &M, &N) != EOF) { init(); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= M; ++i) { cur[i] = 0; int num; for (int j = 1; j <= N; ++j) { //输入时就要按位来存储，cur[i]表示的是第i行整行的情况，每次改变该数字的二进制表示的一位 scanf("%d", &num); //表示第i行第j列的情况（0或1） if (num == 0) //若该格为0 cur[i] += (1 << (N - j)); //则将该位置为1（注意要以相反方式存储，即1表示不可放牧 } } for (int i = 1; i <= top; i++) { if (fit(state[i], 1)) { //判断所有可能状态与第一行的实际状态的逆是否有重合 dp[1][i] = 1; //若第1行的状态与第i种可行状态吻合，则dp[1][i]记为1 } } /* 状态转移过程中，dp[i][k] =Sigma dp[i-1][j] （j为符合条件的所有状态） */ for (int i = 2; i <= M; ++i) { //i索引第2行到第M行 for (int k = 1; k <= top; ++k) { //该循环针对所有可能的状态，找出一组与第i行相符的state[k] if (!fit(state[k], i)) //*****首先筛选与地形没有冲突的state continue; //判断是否符合第i行实际情况 判断障碍与选择是否有冲突 for (int j = 1; j <= top; ++j) { //找到state[k]后，再找一组与第i-1行符合，且与第i行（state[])不冲突的状态state[j] if (!fit(state[j], i - 1))//*****然后筛选与上一行没有冲突的state continue; //判断是否符合第i-1行实际情况 if (state[k] & state[j]) // *****找到两者之后判断两者有没有冲突 continue; //判断是否与第i行冲突 dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod; //若以上皆可通过，则将'j'累加到‘k'上 } } } int ans = 0; for (int i = 1; i <= top; ++i) { //累加最后一行所有可能状态的值，即得最终结果。 ans = (ans + dp[M][i]) % mod; } printf("%d\n", ans); }}