取数游戏

题意

给出一个 N × M 的非负整数矩阵，要从中选出若干个数。

限制是：任意两个被选中的格子不能相邻。这里的“相邻”不只是上下左右，还包括四个对角线方向，也就是 8 个方向都不能碰。

要求这些被选中数字的和最大。

思路

最直接的想法是把每个格子都考虑“选”或“不选”，然后回溯搜索所有合法方案。

这个版本最容易理解题意，也可以用来做小数据对拍：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int T;
int n, m;
long long a[MAXN][MAXN];  // 棋盘权值
int chosen[MAXN][MAXN];   // 是否已经选择这个格子
long long ans;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool can_take(int x, int y) {
    for (int k = 0; k < 8; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && chosen[nx][ny]) {
            return false;
        }
    }
    return true;
}

void dfs(int pos, long long sum) {
    if (pos > n * m) {
        ans = max(ans, sum);
        return;
    }

    int x = (pos - 1) / m + 1;
    int y = (pos - 1) % m + 1;

    // 不选当前格子。
    dfs(pos + 1, sum);

    // 只有和已选格子都不相邻时，才能选当前格子。
    if (can_take(x, y)) {
        chosen[x][y] = 1;
        dfs(pos + 1, sum + a[x][y]);
        chosen[x][y] = 0;
    }
}

long long solve_one_case() {
    memset(chosen, 0, sizeof(chosen));
    ans = 0;
    dfs(1, 0);
    return ans;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        cout << solve_one_case() << '\n';
    }

    return 0;
}

但总格子数最多有 6 × 6 = 36 个，直接枚举所有方案显然太慢。

为什么可以按行做状态压缩

观察一个格子会和哪些格子冲突：

同一行里，它只会和左右两个位置冲突；
相邻两行里，它会和正上、左上、右上这三个位置冲突；
再远的行就不会直接相邻了。

这说明：第 i 行怎么选，只会影响第 i-1 行和第 i+1 行，不会跨两行产生约束。

于是可以把“第 i 行选了哪些列”压成一个二进制状态。

合法行状态

如果某一行选择状态是 mask，那么它在本行内部必须没有相邻的两个 1，也就是：

(mask & (mask << 1)) == 0

这样就保证了同一行中不会选到左右相邻的格子。

两行之间如何判断兼容

设上一行状态是 pre，当前行状态是 cur。

它们要同时满足：

不能在同一列都选：pre & cur == 0
不能形成左上右下对角：(pre << 1) & cur == 0
不能形成右上左下对角：(pre >> 1) & cur == 0

只要这三条都满足，两行就是兼容的。

DP 定义

设：

f[i][j]

表示处理到第 i 行，且第 i 行选择第 j 个合法状态时，前 i 行能得到的最大和。

转移就是：

f[i][j] = max(f[i-1][k] + row_sum[i][j])

其中第 k 个上一行状态必须和第 j 个当前状态兼容。

因为所有权值都是非负数，而且状态 0（这一行一个都不选）一定存在，所以答案一定能在这套 DP 里被覆盖到。

DP 公式

设 $S$ 为所有合法行状态的集合（行内无相邻 $1$ ）， $row\_sum_{i,j}$ 为第 $i$ 行选第 $j$ 个状态时的权值和。令 $f_{i,j}$ 表示处理到第 $i$ 行，且第 $i$ 行选第 $j$ 个状态时的最大和。

初始化：

f_{1,j} = row\_sum_{1,j}

转移：对每个与状态 $j$ 兼容的上一行状态 $k$ ：

f_{i,j} = \max_{compatible(j,k)}(f_{i-1,k} + row\_sum_{i,j})

兼容条件（8 邻接不冲突）：

compatible(j,k) = (j \mathbin{\&} k = 0) \wedge ((j \ll 1) \mathbin{\&} k = 0) \wedge ((j \gg 1) \mathbin{\&} k = 0)

最终答案为：

\max_j f_{n,j}

样例 DP 表格

以第三组样例 $3 \times 3$ 矩阵为例：

text

$m = 3$ 时合法行状态共 5 个：000(0), 001(1), 010(2), 100(4), 101(5)。

行 $i$	状态 $j$	二进制	$row\_sum$	$f_{i,j}$	最优来源 $k$
1	0	`000`	0	0	—
1	1	`001`	1	1	—
1	2	`010`	1	1	—
1	4	`100`	1	1	—
1	5	`101`	2	2	—
2	0	`000`	0	2	任何 $k$ （取 $f_{1,5}=2$ ）
2	1	`001`	1	2	$k=4$ （ $f_{1,4}+1=2$ ）
2	2	`010`	99	99	$k=0$ （ $f_{1,0}+99=99$ ）
2	4	`100`	1	2	$k=1$ （ $f_{1,1}+1=2$ ）
2	5	`101`	2	2	$k=0$ （ $f_{1,0}+2=2$ ）
3	0	`000`	0	99	$k=2$ （ $f_{2,2}+0=99$ ）
3	1	`001`	1	3	$k=0$ 或 $k=4$ （ $f_{2,0}+1=3$ ）
3	2	`010`	1	3	$k=0$ （ $f_{2,0}+1=3$ ）
3	4	`100`	1	3	$k=0$ 或 $k=1$ （ $f_{2,0}+1=3$ ）
3	5	`101`	2	4	$k=0$ （ $f_{2,0}+2=4$ ）

答案 $\max(f_{3,j}) = 99$ ，对应第 2 行选中间格 99，其余行不选。

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXS = 70;

int T;
int n, m;
long long a[MAXN][MAXN];      // 棋盘权值
int st[MAXS], state_cnt;      // 所有合法行状态
long long row_sum[MAXN][MAXS];
long long f[MAXN][MAXS];      // f[i][j]：处理到第 i 行，且第 i 行选状态 j 的最大和

bool valid_state(int s) {
    return (s & (s << 1)) == 0;
}

bool compatible(int a, int b) {
    if (a & b) {
        return false;
    }
    if ((a << 1) & b) {
        return false;
    }
    if ((a >> 1) & b) {
        return false;
    }
    return true;
}

void build_states() {
    state_cnt = 0;
    for (int s = 0; s < (1 << m); s++) {
        if (valid_state(s)) {
            st[++state_cnt] = s;
        }
    }
}

void calc_row_sum() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= state_cnt; j++) {
            row_sum[i][j] = 0;
            int mask = st[j];
            for (int k = 0; k < m; k++) {
                if (mask & (1 << k)) {
                    row_sum[i][j] += a[i][k + 1];
                }
            }
        }
    }
}

long long solve_one_case() {
    build_states();
    calc_row_sum();

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= state_cnt; j++) {
            f[i][j] = -1;
        }
    }

    for (int j = 1; j <= state_cnt; j++) {
        f[1][j] = row_sum[1][j];
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= state_cnt; j++) {
            for (int k = 1; k <= state_cnt; k++) {
                if (f[i - 1][k] == -1) {
                    continue;
                }
                if (!compatible(st[j], st[k])) {
                    continue;
                }
                f[i][j] = max(f[i][j], f[i - 1][k] + row_sum[i][j]);
            }
        }
    }

    long long ans = 0;
    for (int j = 1; j <= state_cnt; j++) {
        ans = max(ans, f[n][j]);
    }
    return ans;
}

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

    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        cout << solve_one_case() << '\n';
    }

    return 0;
}

复杂度

时间复杂度： $O(n · S^2)$
空间复杂度： $O(n · S)$

其中 S 是一行的合法状态个数。m <= 6 时，S 很小，所以这个做法非常轻松。

总结

这题的关键在于看出“8 邻接”的约束其实只会影响当前行和相邻行。

一旦把每一行压成二进制状态，问题就变成了经典的“按行枚举行状态，再检查相邻两行兼容”的状态压缩 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路