[SCOI2005] 互不侵犯

题意

在 $N\times N$ 棋盘放 $K$ 个国王，国王攻击周围 $8$ 格。求互不攻击的方案数。 $N\leqslant 9$ ， $K\leqslant N^2$ 。

思路

$N\leqslant 9$ 但直接枚举 $N\times N$ 格子的 01 序列是 $2^{N^2}$ ，完全不可行。先看一个只适合小数据的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * date: 2026-07-07 00:00:00
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举每个格子是否放国王。
#include <bits/stdc++.h>
using namespace std;

int n, k;
int board[10][10];   // board[r][c] = 1 表示 (r,c) 放国王
int choose_cnt;       // 当前已放国王数
long long ans;

// 检查 (r,c) 放国王是否与已放置的冲突（只检查上方和左方）
bool can_place(int r, int c) {
    for (int dr = -1; dr <= 1; dr++) {
        for (int dc = -1; dc <= 1; dc++) {
            if (dr == 0 && dc == 0) continue;
            int nr = r + dr, nc = c + dc;
            if (nr >= 1 && nr <= n && nc >= 1 && nc <= n) {
                if (board[nr][nc] == 1) return false;
            }
        }
    }
    return true;
}

// 按行优先顺序递归枚举每个格子
void dfs(int r, int c) {
    if (r > n) {
        // 所有格子处理完
        if (choose_cnt == k) ans++;
        return;
    }

    int nr = r, nc = c + 1;
    if (nc > n) { nr++; nc = 1; }

    // 选择1：不放国王
    board[r][c] = 0;
    dfs(nr, nc);

    // 选择2：放国王
    if (choose_cnt < k && can_place(r, c)) {
        board[r][c] = 1;
        choose_cnt++;
        dfs(nr, nc);
        choose_cnt--;
        board[r][c] = 0;
    }
}

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

    cin >> n >> k;
    dfs(1, 1);
    cout << ans << '\n';
    return 0;
}

暴力按行优先顺序递归枚举每个格子选或不选，放置前检查周围 8 格是否冲突。这个写法只适合 $N\leqslant 4$ 验证数据。

状态压缩

每一行只有 $N\leqslant 9$ 个格子，可以把一行的国王摆放方案压缩成一个二进制数（bitmask）。第 $i$ 位为 $1$ 表示该列放国王。

单行约束：同一行相邻两格不能都有国王，即 (mask & (mask << 1)) == 0。

设 $S$ 为所有满足单行约束的合法 mask 集合。 $N=9$ 时 $|S|$ 不到 $90$ 个。

DP 定义与转移

设 dp[row][mask][cnt]：前 row 行，第 row 行摆放状态为 mask，总共放了 cnt 个国王的方案数。

转移：从第 row-1 行的 prev 状态转移到第 row 行的 cur 状态，需要满足：

正上方不冲突：(cur & prev) == 0
左上方不冲突：((cur << 1) & prev) == 0
右上方不冲突：((cur >> 1) & prev) == 0

第 1 行初始化：dp[1][mask][popcount(mask)] = 1（对每个合法 mask）。

最终答案： $\sum_{mask \in S} dp[n][mask][k]$ 。

样例 DP 状态转移表

以 $N=3, K=2$ 的样例为例，下表展示部分关键行的 DP 转移：

row	cur (二进制)	国王数	来自 prev	dp[row][cur][cnt] 累计值
1	000 (0)	0	—	1
1	001 (1)	1	—	1
1	010 (2)	1	—	1
1	100 (4)	1	—	1
1	101 (5)	2	—	1
2	000 (0)	0	0/2/5	总计行1所有 cnt=0→3 份
2	010 (2)	1	0	dp[1][0][0] = 1
2	010 (2)	2	1,4	1+1 = 2
2	000 (0)	1	1,2,4	3
…	…	…	…	…

重点观察：第 2 行 cur=010 时，只能从第 1 行那些不与 010 冲突的 prev 转移过来。比如 prev=001（第 1 列有王）会与 cur=010 的左上方冲突，因此 prev=1 不可作为转移来源。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * date: 2026-07-07 00:00:00
 */
// main.cpp：状态压缩 DP，逐行转移。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXK = 85;
const int MAXS = 1 << 9;  // N ≤ 9

int n, k;
long long dp[MAXN][MAXS][MAXK];  // dp[row][mask][cnt]

// valid_one[mask] = 1 表示 mask 中没有任何相邻的 1
int valid_one[MAXS];
// king_cnt[mask] = mask 中 1 的个数
int king_cnt[MAXS];
// valid_sets 保存所有合法的单行状态
vector<int> valid_sets;

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

    cin >> n >> k;

    // 预处理所有合法的单行状态
    for (int mask = 0; mask < (1 << n); mask++) {
        if (mask & (mask << 1)) continue;  // 同一行有相邻国王
        valid_one[mask] = 1;
        king_cnt[mask] = __builtin_popcount(mask);
        valid_sets.push_back(mask);
    }

    // 第 1 行初始化
    for (int mask : valid_sets) {
        if (king_cnt[mask] <= k) {
            dp[1][mask][king_cnt[mask]] = 1;
        }
    }

    // 逐行 DP
    for (int row = 2; row <= n; row++) {
        for (int cur : valid_sets) {
            int cnt_cur = king_cnt[cur];
            if (cnt_cur > k) continue;

            for (int prev : valid_sets) {
                // 检查上下行冲突
                if ((cur & prev) || ((cur << 1) & prev) || ((cur >> 1) & prev)) continue;

                for (int c = cnt_cur; c <= k; c++) {
                    dp[row][cur][c] += dp[row - 1][prev][c - cnt_cur];
                }
            }
        }
    }

    // 汇总答案
    long long ans = 0;
    for (int mask : valid_sets) {
        ans += dp[n][mask][k];
    }

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

复杂度

预处理合法 mask： $O(2^N)$
DP 转移： $O(N \cdot |S|^2 \cdot K)$ ， $|S| \approx 90$ ， $N=9$ ， $K\leqslant 81$ ，实际约 $9 \times 8100 \times 81 \approx 5.9\times 10^6$ 次运算
空间复杂度： $O(N \cdot |S| \cdot K)$ , 可用滚动数组优化到 $O(|S| \cdot K)$

总结

状压 DP 的经典特征： $N$ 很小（通常 $\leqslant 20$ ），且状态可以用"一行/一列"为单位处理。本题中 $N\leqslant 9$ 是关键提示。核心步骤：

把一行压缩为 bitmask
预处理单行合法状态
定义 dp[row][mask][附加信息]，按行转移
用位运算快速判断行间冲突