426 状态压缩DP 玉米田【动态规划】

老师给的代码没有滚动数组优化，老习惯，强迫症。show you my code

```C++

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int P = 1e9;

int n, m;     //行数，列数

int g[13];    //各行的状态值

int cnt;      //同一行的合法状态个数

int s[1 << 13]; //一行的合法状态集

int f[2][1 << 13];

//f[i,a]表示已经种植前i行，第i行第a个状态时的方案数

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++) {

            int x;

            cin >> x;

            g[i] = (g[i] << 1) + x; //各行的状态值

        }

    for (int i = 0; i < (1 << m); i++) //枚举一行所有状态

        if (!(i & i >> 1))      //如果不存在相邻的1

            s[cnt++] = i;         //保存一行的合法状态

    f[0 & 1][0] = 1;

    for (int i = 1; i <= n + 1; i++) //枚举行

        for (int a = 0; a < cnt; a++) { //枚举第i行合法状态

            f[i & 1][a] = 0;

            for (int b = 0; b < cnt; b++) //枚举第i-1行合法状态

                if (!(s[a]&s[b])        //不能同列均为1

                    && (s[a]&g[i]) == s[a]) //种在肥沃土地上

                    f[i & 1][a] = (f[i & 1][a] + f[(i - 1) & 1][b]) % P;

        }

    printf("%d\n", f[(n + 1) & 1][0]);

    return 0;

}

```