[USACO06NOV] Corn Fields G

GitHub跳转原题关系图返回列表

把每一行压成二进制状态，预处理单行合法状态后按行做状压 DP，统计所有不相邻的种草方案数。

OJ: luogu

题目 ID: P1879

难度:普及+/提高

标签:状态压缩动态规划计数DP网格DP

日期: 2026-06-21 05:51

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给定一个 n x m 的农田网格。

1 表示这块地可以种草，0 表示不能种草。

要求统计所有合法种草方案数，满足：

  • 只能在 1 的位置种草
  • 任意两块种草的格子不能有公共边

空方案也算一种，答案对 100000000 取模。

思路

先看一个适合小数据理解和对拍的暴力：

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

const int MOD = 100000000;

int n, m;
int a[15][15];
int used[15][15];
int ans;

bool ok_place(int x, int y) {
    if (a[x][y] == 0) {
        return false;
    }
    if (y > 1 && used[x][y - 1]) {
        return false;
    }
    if (x > 1 && used[x - 1][y]) {
        return false;
    }
    return true;
}

void dfs_cell(int pos) {
    if (pos == n * m) {
        ans++;
        if (ans >= MOD) {
            ans -= MOD;
        }
        return;
    }

    int x = pos / m + 1;
    int y = pos % m + 1;

    // 不在这个格子种草。
    dfs_cell(pos + 1);

    // 在这个格子种草。
    if (ok_place(x, y)) {
        used[x][y] = 1;
        dfs_cell(pos + 1);
        used[x][y] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：逐格枚举种或不种，用来帮助理解题意和辅助对拍。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    memset(used, 0, sizeof(used));
    ans = 0;
    dfs_cell(0);
    cout << ans << '\n';
    return 0;
}

暴力会逐格枚举“种”或“不种”，如果当前格子能种，并且和上方、左方都不冲突，就尝试放下去。

但正解不能逐格做，因为总状态接近 2^(n*m)。

这题真正该利用的是：限制只有上下左右相邻，所以当我们按行处理时：

  • 同一行内部只需要保证没有相邻的两个 1
  • 当前行只会和上一行发生纵向冲突

于是可以把每一行压成一个二进制状态 mask。

先预处理所有单行合法状态 s，要求：

s & (s << 1) == 0

然后按行 DP，设当前行状态为 cur，上一行状态为 pre。

只要满足：

  • cur 只在可种位置上取 1
  • cur & pre == 0

就可以从上一行状态转移过来。

DP 转移方程

按行滚动时，若 cur 是当前行合法状态，pre 是上一行合法状态，且 cur & pre == 0，则：

ndp[cur]=(ndp[cur]+dp[pre]) mod 100000000 ndp[cur] = (ndp[cur] + dp[pre]) \bmod 100000000

初始可以看成第 0 行状态为 0，答案是最后一行所有状态之和。

因为只依赖上一行，所以直接用滚动数组即可。

代码

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

const int MOD = 100000000;
const int MAXN = 15;
const int MAXS = 1 << 12;

int n, m;
int allow_mask[MAXN];        // allow_mask[i] 的 1 表示这一格可以种草
int states[MAXS], state_cnt; // 所有单行内部合法状态
int dp[2][MAXS];

bool ok_self(int s) {
    // 同一行里不能出现相邻的两块草地。
    return (s & (s << 1)) == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int full = 1 << m;
    for (int s = 0; s < full; s++) {
        if (ok_self(s)) {
            states[state_cnt++] = s;
        }
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int row = 1; row <= n; row++) {
        int now = row & 1;
        int pre = now ^ 1;
        memset(dp[now], 0, sizeof(dp[now]));

        for (int i = 0; i < state_cnt; i++) {
            int cur = states[i];
            // 当前行选的位置必须全部是可种草的土地。
            if ((cur & allow_mask[row]) != cur) {
                continue;
            }

            for (int j = 0; j < state_cnt; j++) {
                int last = states[j];
                // 上下两行不能在同一列都种草。
                if (cur & last) {
                    continue;
                }
                dp[now][cur] += dp[pre][last];
                if (dp[now][cur] >= MOD) {
                    dp[now][cur] -= MOD;
                }
            }
        }
    }

    int last = n & 1;
    int ans = 0;
    for (int i = 0; i < state_cnt; i++) {
        ans += dp[last][states[i]];
        if (ans >= MOD) {
            ans -= MOD;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设单行合法状态数为 S，时间复杂度为 O(n∗S2)O(n * S^2)，空间复杂度为 O(S)O(S)。

总结

这题是“按行状压计数”的基础模板题。

关键在于把“格子之间不能相邻”改写成“单行合法 + 相邻两行兼容”，这样就能自然落到状压 DP 上。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析