POJ 3254 Corn Fields：狀壓 DP 求合法種植方案數

n×m 矩陣 (≤12×12) 種玉米，相鄰格不可同時種，部分格子禁種。求方案數模 100,000,000。

狀態壓縮 DP

• 每行狀態用 m 位二進制表示，1 為種植
• 合法狀態：無相鄰 1 (!(s & (s<<1))) 且不與禁種位衝突
• 預計算所有合法狀態（m=12 時最多 377 個）
• 行間轉移：dp[i][curr] += dp[i-1][prev]，條件 (curr & prev) == 0

完整代碼

#include <iostream>
#include <cstring>
using namespace std;
const int inf = 100000000;
int rem[15][15], legal[10000], num[20], ans[20][10000];
int n, m, p;

bool OK(int s) { return !(s & (s<<1)); }

int main() {
    scanf("%d%d", &n, &m);
    for (int i=0; i

優化提示

預計算兼容狀態列表 compat[j] = {k | (legal[j]&legal[k])==0}，轉移時只遍歷兼容態
滾動數組優化空間至 O(p)

狀壓 DP 是處理網格相鄰約束問題的核心方法，本題為入門級模板。