POJ 3254 Corn Fields：狀壓 DP + 滾動數組計數放牛方案

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000000;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector land(n);
    for (int i = 0; i < n; ++i) {
        int mask = 0;
        for (int j = 0; j < m; ++j) {
            int x; cin >> x;
            if (x) mask |= 1 << j;
        }
        land[i] = mask;
    }
    vector> valid(n);
    int ALL = 1 << m;
    for (int i = 0; i < n; ++i) {
        for (int s = 0; s < ALL; ++s) {
            if ((s & (s<<1)) == 0 && (s & ~land[i]) == 0)
                valid[i].push_back(s);
        }
    }
    vector dp(ALL), ndp(ALL);
    for (int s : valid[0]) dp[s] = 1;
    for (int i = 1; i < n; ++i) {
        fill(ndp.begin(), ndp.end(), 0);
        for (int s : valid[i]) {
            for (int t : valid[i-1]) {
                if ((s & t) == 0) {
                    ndp[s] += dp[t];
                    if (ndp[s] >= MOD) ndp[s] -= MOD;
                }
            }
        }
        dp.swap(ndp);
    }
    int ans = 0;
    for (int s : valid[n-1]) {
        ans += dp[s];
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
    return 0;
}

複雜度

• 狀態數 ≤ 2¹² = 4096，實際合法狀態約 300~500。
• 轉移：O(N × |valid|²) ≈ 12 × 500² = 3e6，極快。
• 空間：O(2^M)。

關鍵點

• 位運算判斷合法：(s & (s<<1)) == 0 檢查水平相鄰，(s & t) == 0 檢查垂直相鄰。
• 滾動數組將空間從 O(N·2^M) 降至 O(2^M)。
• 模 10⁸ 非質數，僅做加法取模。

這題是狀壓 DP 入門經典題，展示了「逐行狀態 + 相容性轉移」的標準框架，滾動數組優化空間是必備技巧。