BZOJ 1087 [SCOI2005] 互不侵犯 King：狀壓 DP

問題大意

N×N 棋盤放 K 個國王，互不攻擊（八方向相鄰不可）。N ≤ 9，求方案數。

狀態壓縮 DP

1. 預處理合法行狀態：DFS 枚舉單行放置方案，無相鄰 1。狀態數最多 2^9=512，實際合法極少。
2. 預處理行間衝突：兩行狀態 s1, s2 衝突條件：(s1 & s2) || (s1<<1 & s2) || (s1>>1 & s2)。
3. DP 轉移：f[row][k][state] 表示前 row 行放 k 個、第 row 行狀態為 state 的方案數。轉移枚舉上一行合法狀態。

代碼

#include <cstdio>
#define MAXN 100
long long f[MAXN][MAXN][600], ans;
int stay[MAXN], cnt[MAXN], map[MAXN][MAXN];
int n, k, m = 0;

void pre_dfs(int x, int pos, int now) {
    stay[++m] = now; cnt[m] = x;
    if (x >= (n+1)/2 || x >= k) return;
    for (int i = pos+2; i <= n; i++)
        pre_dfs(x+1, i, now | (1<<(i-1)));
}

void pre_map() {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            map[i][j] = map[j][i] = ((stay[i]&stay[j]) || ((stay[i]>>1)&stay[j]) || ((stay[i]<<1)&stay[j])) ? 0 : 1;
    for (int i = 1; i <= m; i++) f[1][cnt[i]][i] = 1;
}

int main() {
    scanf("%d%d", &n, &k);
    pre_dfs(0, -1, 0); pre_map();
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= k; j++)
            for (int now = 1; now <= m; now++) {
                if (cnt[now] > j) continue;
                for (int h = 1; h <= m; h++)
                    if (map[h][now] && cnt[h] + cnt[now] <= j)
                        f[i][j][now] += f[i-1][j-cnt[now]][h];
            }
    for (int i = 1; i <= m; i++) ans += f[n][k][i];
    printf("%lld\n", ans); return 0;
}

注意

• 答案可能超 int，需用 long long。
• DFS 狀態生成利用「間隔至少一格」剪枝。