状压 DP:dp[S][p] 记已取集合与停留格的最大得分,转移为走相邻未取格或在边缘格离开方格重新入口,取数得分按 k×value 累加。
OJ: roj
题目 ID: 1685
难度:提高
标签:动态规划状压DP网格DP位运算python
创建: 2026-10-07 15:31
更新: 2026-10-07 15:31
形式化题目
给定
游戏的走法是一个取数序列
(第一步必须从边缘格取); - 对每个
,要么 与 在方格中上下左右相邻,要么 且 (前一步停在边缘时,可以"离开方格"再从任一未取的边缘格重新进入)。
一次取数只允许发生在这两种情况下;序列可以提前终止(取完所有数,或再也走不动、不想走),也就是说任何合法前缀都是一个合法的游戏过程。
得分规则:若
注意"边缘 + 相邻"的连通性使序列并非任意排列。以样例 1 为例,答案是依次取
正解
思路
先想暴力:枚举所有取数序列并检查合法性。合法序列数量最坏到
- 走到哪了只取决于"哪些格子已经取走"和"当前站在哪一格"。已经取走的集合只有
种,当前格只有 种,状态总量 ——完全在可承受范围内。 - 得分的系数(第几次取)不受状态以外的东西影响:取走
个格子后,下一个取走的数一定是第 个,得分系数自动是 ,不需要额外记录步数。
于是定义
其中要求
转移时用刷表法(从已有状态推向更大集合)。设
- 走到相邻的未取格
: ; - 离开方格再重新进入:仅当
在边缘时可用,此时 可以是任意未取的边缘格,同样是 。
两条规则是"或"的关系,写代码时可以把候选
集合只增不减,所以按
答案取所有
下面用 - 表示不可达:
0001 |
1 | - | - | - |
0011 |
4 | 5 | - | - |
0101 |
5 | - | 7 | - |
0110 |
- | 7 | 8 | - |
0111 |
11 | 13 | 14 | - |
1000 |
- | - | - | 4 |
1011 |
13 | 15 | - | 17 |
1100 |
- | - | 10 | 11 |
1101 |
14 | - | 18 | 19 |
1110 |
- | 17 | 19 | 20 |
1111 |
24 | 27 | 29 | 30 |
观察两件事。第一,形如 0001 / 1000 的单元素集合每行只有一个入口,因为第一个数必须从边缘格取,这里四个格都是边缘格所以都有值。第二,1111 行即取完四格的结果,
代码
Python 版:
#!/usr/bin/env python3
# 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
# create_at: 2026-10-07 15:27
# update_at: 2026-10-07 15:27
import sys
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type States = dict[int, int] # 某个已取集合下"当前停在哪格 -> 该集合的最大得分"
type Nbrs = list[list[int]] # 邻接表:nbrs[i] 是格子 i 四个方向里仍在方格内的相邻格编号
def max_score(values: list[int], nbrs: Nbrs, on_edge: list[bool], edge: list[int]) -> int:
"""状压 DP,回答"最大总得分是多少"。
dp[S][p] = 已取格集合为 S、当前停在格 p 时的最大得分。转移有两类:
走到相邻未取格;当前在边缘格时离开方格,从任一未取边缘格重新进入。
第 k 次取走的格 q 得分 k * values[q],所以用 S.bit_count() + 1 直接乘。
"""
total = len(values)
dp: dict[int, States] = {}
for p in edge: # 第 1 次取数必须从边缘格入手,得 1 * values[p]
dp[1 << p] = {p: values[p]}
for mask in range(1 << total): # 集合只增不减,按掩码从小到大推进就是拓扑序
states = dp.get(mask)
if not states: # 该集合一个状态都到不了,跳过
continue
k = mask.bit_count() + 1 # 下一个取走的数是第 k 个
for p, cur in states.items():
moves = [q for q in nbrs[p] if not mask >> q & 1] # 走到相邻未取格
if on_edge[p]: # 停在边缘:可离格再入口
moves += [q for q in edge if not mask >> q & 1]
for q in moves:
nxt = cur + k * values[q]
# 所有可达状态得分都非负,用 0 当"尚未到达"的下界即可,真到达时只会更大
nxt_states = dp.setdefault(mask | 1 << q, {})
nxt_states[q] = max(nxt_states.get(q, 0), nxt)
scores = [v for st in dp.values() for v in st.values()]
return max(scores, default=0) # 游戏可随时结束,一个数都不取时得 0 分
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
m, n = next(data), next(data)
total = m * n
values = [next(data) for _ in range(total)]
cells = [divmod(i, n) for i in range(total)] # 每格展平编号 -> (行, 列)
on_edge = [r in (0, m - 1) or c in (0, n - 1) for r, c in cells]
edge = [i for i, ok in enumerate(on_edge) if ok] # 所有边缘格的编号
nbrs: Nbrs = []
for i, (r, c) in enumerate(cells):
around = ((i - n, r > 0), (i + n, r < m - 1), # 上、下
(i - 1, c > 0), (i + 1, c < n - 1)) # 左、右
nbrs.append([j for j, inside in around if inside]) # 只留还在方格内的方向
print(max_score(values, nbrs, on_edge, edge))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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
* create_at: 2026-10-07 15:27
* update_at: 2026-10-07 15:27
*/
// main.cpp:新版方格取数。
// 状压 DP:dp[S][p] = 已取走的格子集合为 S、当前停在格 p 时的最大得分。
// 转移有两类:走到相邻未取格;当前在边缘格时"离开方格",从任一未取边缘格重新进入。
// 每步取走第 k 个数得分 k * value[q],所以刷表时用 k = popcount(S) + 1 直接乘。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXCELL = 16; // 格子数上限:m*n <= 16
const int MAXMASK = 1 << MAXCELL; // 集合掩码上限:2^16
int m, n; // m 行 n 列(题面顺序)
int total; // 格子总数 m*n,把方格按行展平后第 i 格是第 i/n 行第 i%n 列
ll value[MAXCELL]; // value[i]:第 i 格里写的数
bool onEdge[MAXCELL]; // onEdge[i]:第 i 格是否位于方格边缘(只有边缘格能当起点或重新入口)
int nbr[MAXCELL][4]; // nbr[i][d]:第 i 格四个方向上的邻居编号,-1 表示越出方格
ll dp[MAXMASK][MAXCELL]; // dp[S][p]:已取集合 S、当前停在格 p 的最大得分;-1 表示该状态不可达
// 预处理每个格子的上下左右邻居编号,越界的记为 -1
void build_neighbors() {
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
for (int i = 0; i < total; i++) {
int r = i / n, c = i % n;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
bool inside = (nr >= 0 && nr < m && nc >= 0 && nc < n);
nbr[i][d] = inside ? nr * n + nc : -1;
}
}
}
// 用候选得分 val 去松弛 dp[S][p]:状态可能由多条取数顺序到达,取最大值
void relax(int S, int p, ll val) {
if (val > dp[S][p]) dp[S][p] = val;
}
// 状压 DP 主体:返回最大总得分(一个数都不取时得 0 分,游戏允许中途结束)
ll solve_dp() {
memset(dp, -1, sizeof(dp)); // 得分为非负,用 -1 标记不可达
for (int p = 0; p < total; p++) {
if (onEdge[p]) dp[1 << p][p] = value[p]; // 第 1 次取数必须从边缘格入手,得 1 * value[p]
}
ll ans = 0; // 游戏可以一开始就结束,也可以走到无路可走时结束
for (int S = 1; S < (1 << total); S++) {
for (int p = 0; p < total; p++) {
ll cur = dp[S][p];
if (cur < 0) continue; // 该状态不可达
int k = __builtin_popcount(S) + 1; // 已取 popcount(S) 个,下一个取走的是第 k 个
for (int d = 0; d < 4; d++) { // (1) 走到相邻的未取格
int q = nbr[p][d];
if (q < 0 || (S >> q & 1)) continue;
relax(S | 1 << q, q, cur + k * value[q]);
}
if (onEdge[p]) { // (2) 停在边缘格:可以离开方格再重新进入
for (int q = 0; q < total; q++) {
if (!onEdge[q] || (S >> q & 1)) continue;
relax(S | 1 << q, q, cur + k * value[q]);
}
}
if (cur > ans) ans = cur; // 当前状态就是一个合法的结束时刻
}
}
return ans;
}
int main() {
if (scanf("%d %d", &m, &n) != 2) return 0;
total = m * n;
for (int i = 0; i < total; i++) scanf("%lld", &value[i]);
for (int i = 0; i < total; i++) {
int r = i / n, c = i % n;
onEdge[i] = (r == 0 || r == m - 1 || c == 0 || c == n - 1);
}
build_neighbors();
printf("%lld\n", solve_dp());
return 0;
}复杂度
状态数
总结
本题的关键观察是:状态只需要"已取集合