POJ 3254：Corn Fields - 狀態壓縮 DP 入門

問題描述

在 n × m 的網格中放牧，某些格子不可用。要求：同行相鄰格子不能同時放牧；上下相鄰行的同列也不能同時放牧。求合法放牧方案數模 10^9。

狀態壓縮思想

• 每行狀態用 m 位二進制數表示，1 表示放牧，0 表示不放。
• 合法行狀態：無相鄰 1，即 (state & (state << 1)) == 0；且不與該行禁用格子衝突。
• 相鄰行狀態兼容：(state_i & state_{i-1}) == 0（無列衝突）。

DP 定義與轉移

dp[i][s]：前 i 行，第 i 行狀態為 s 的方案數。

轉移：dp[i][s] = Σ dp[i-1][t]，其中 s 合法、t 合法、s & t == 0。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000000;
const int MAXM = 12; // m ≤ 12
const int MAXS = 1 << MAXM;

int n, m;
int valid[MAXS], vc; // 合法狀態列表
int forbidden[15]; // 每行禁用掩碼
int dp[15][MAXS];

int main() {
    while (cin >> n >> m) {
        vc = 0;
        for (int s = 0; s < (1<> x;
                if (x == 0) forbidden[i] |= 1 << (j-1);
            }
        }

        memset(dp, 0, sizeof(dp));
        for (int s : valid) if ((s & forbidden[1]) == 0) dp[1][s] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int s : valid) if ((s & forbidden[i]) == 0) {
                for (int t : valid) if ((t & forbidden[i-1]) == 0 && (s & t) == 0) {
                    dp[i][s] = (dp[i][s] + dp[i-1][t]) % MOD;
                }
            }
        }

        int ans = 0;
        for (int s : valid) ans = (ans + dp[n][s]) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

優化技巧

• 預計算所有合法狀態列表 valid[]，減少無效枚舉。
• 預計算兼容轉移表 compat[s]，進一步加速（本題 m≤12 狀態數 ≤ 377，直接雙循環足夠快）。

總結

狀態壓縮 DP 經典入門題：行狀態合法性檢查、行間兼容性檢查、DP 轉移。掌握位運算技巧（&, <<, |）是關鍵。