洛谷题单指南-状态压缩动态规划-P1879 [USACO06NOV] Corn Fields G

原题链接：https://www.luogu.com.cn/problem/P1879

题意解读：在m*n的区域种玉米，能种的是1不能种的是0，要求玉米不能种在相邻格子，求一共有多少种法，模100000000。

解题思路：

用状态压缩来表示一行玉米的种植情况，二进制中1表示种了，0表示没种。

对于一行状态，可以判断其合法性：相邻不能有连续1，在不能种的格子不能有1。

状态转移也很简单，通过枚举两行的合法状态，然后看两行状态是否存在上下相邻的1，不存在则可以转移。

状态表示：设f[i][j]表示前i行已种完，且第i行的状态为j的方案数

初始化：f[0][0] = 1，不种也是一种方案

状态转移：枚举所有第i行的状态j，枚举所有第i-1行的状态k，f[i][j] += f[i - 1][k]

结果：多枚举一行，枚举到第m+1行，答案是f[m + 1][0]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 15, MOD = 1e8;

int mask[N];
int f[N][1 << 12];
vector<int> stat; //所有合法的状态
vector<int> mp[1 << 12]; //所有合法的状态转移
int m, n;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int x;
            cin >> x;
            if(x == 0) mask[i] |= (1 << j);
        }
    }

    //找到所有合法状态
    for(int i = 0; i < 1 << n; i++)
    {
        if(i & i << 1) continue; //存在左右相邻的1
        stat.push_back(i);
    }

    //找到所有合法的状态转移
    for(auto i : stat)
    {
        for(auto j : stat)
        {
            if(i & j) continue; //存在上下相邻的1
            mp[i].push_back(j);
        }
    }

    f[0][0] = 1;
    for(int i = 1; i <= m + 1; i++)
    {
        for(auto j : stat)
        {
            if(mask[i] & j) continue; //第i行存在不能种的土地
            for(auto k : mp[j])
            {
                if(mask[i - 1] & k) continue; //第i - 1行存在不能种的土地
                f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;
            }
        }
    }

    cout << f[m + 1][0];
    return 0;
}