P1879 [USACO06NOV]玉米田Corn Fields
[原题地址](https://www.luogu.com.cn/problem/P1879)

## 思路
### 状态压缩DP  
可以用一个n位二进制数表示一行的一种种植状态, 如010表示n = 3时在中间位置种植, 旁边两个位置不种植的状态.  
对于长为n的一行, 若不考虑有些位置不可以种植以及不能够相邻种植的约束, 那么总共有1 << n(2的n次方)种植状态.  
所以代码中首先初始化, 遍历长为n的一行的所有种植状态, 即遍历在[0, 1 << n)范围内的整数. 对于[0, 1 << n)中的整数i, 若 (i & (i << 1))不等于0, 则i的二进制表达式中存在连续的1, 也就是i表示的状态存在相邻种植, 是不可以使用这种状态的.而除这种状态之外的所有状态, 则存储到status数组中.  
对于每一行, 输入了可以种植与不可种植的位置, 用一个整数表示一行的情况, 该整数的每一个二进制位对应一个位置是否可以种植, 0表示可以, 1表示不可以(注意根输入的表示相反), 使用数组row, row[i]为表达第i行情况的整数. 那么对于status中的每个状态, 若status[j] & row[i] == 0, 就表示第j种状态适用于第i行.  
然后开始DP. dp[i][j]表示第i行选择status中的第j种状态的方案数量. 第0行进行特殊处理, 其余每行i, 遍历status中的状态, 若row[i] & status[j] == 0, 则第j种状态可以在第i行中实现, 此时对于第i - 1行(上一行), 再次遍历status中的状态, 若row[i - 1] & status[k] == 0, 即第k种状态适用于第i - 1行, 此时若status[j] & status[k] == 0, 意思就是第i行选择的第j种状态和第i - 1行选择的第k种状态是兼容的, 不会造成上下行相邻种植. 那么dp[i][j]就要加上dp[i - 1][k]. 
更多见代码注释. 

## 代码

```c
#include "stdio.h"
#include "stdlib.h"

#define maxm 12
#define maxnum 0x1000 /* 1 << 12 */
#define mod 100000000

int status[maxnum], top;
int row[maxm];
int dp[maxm][maxnum];

//初始化
void init(int n) {
    int p = 1 << n; //最多可能的种植状态数量
    top = 0;
    for (int i = 0; i < p; i++) { //遍历每种状态
        //若没有相邻种植, 则记录i
        if (!(i & (i << 1))) status[top++] = i;
    }
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    init(n);
    int flag;
    for (int i = 0; i < m; i++) {        
        for (int j = 0; j < n; j++) {
            scanf("%d", &flag); //输入, 1表示可以种植, 0表示不可以
            //row[i]的二进制位, 1表示不可种植, 0表示可以
            //初始时row[i]=0, 所有二进制位为0
            if (!flag) row[i] += (1 << (n - j - 1)); //输入为0, 则row[i]相应的二进制位更新为1
        }
    }
    //对于第0行特殊处理
    for (int i = 0; i < top; i++) {        
        if (!(status[i] & row[0])) dp[0][i] = 1; //若status[i]适用于第0行
    }
    for (int i = 1; i < m; i++) { //遍历1至m-1行
        for (int j = 0; j < top; j++) {
            if (status[j] & row[i]) continue; //status[j]不适用于第i行, 则continue
            //找到一个适用于第i行的status[j]
            for (int k = 0; k < top; k++) {
                if (status[k] & row[i - 1]) continue; //status[k]不适用于第i - 1行, 则continue
                //找到一个适用于第i - 1行的status[k]
                if (status[j] & status[k]) continue; //若status[j]与status[k]不兼容, 则continue
                //到这里第i行选择的第j种状态和第i - 1行选择的第k种状态是兼容的
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= mod;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < top; i++) {
        res += dp[m - 1][i];
        res %= mod;
    }
    printf("%d", res);
    return 0;
}
```