新版方格取数

GitHub跳转原题关系图返回列表

状压 DP:dp[S][p] 记已取集合与停留格的最大得分,转移为走相邻未取格或在边缘格离开方格重新入口,取数得分按 k×value 累加。

OJ: roj

题目 ID: 1685

难度:提高

标签:动态规划状压DP网格DP位运算python

创建: 2026-10-07 15:31

更新: 2026-10-07 15:31

形式化题目

给定 mm 行 nn 列的方格,第 ii 行第 jj 列写有非负整数 ai,ja_{i,j},满足 m×n⩽16m \times n \leqslant 16。把方格按行展平成编号 0,1,…,mn−10, 1, \dots, m n - 1 的格子集合 VV,并按 i∈{0,m−1}i \in \{0, m-1\} 或 j∈{0,n−1}j \in \{0, n-1\} 划分出边缘格集合 EE。

游戏的走法是一个取数序列 p1,p2,…,ptp_1, p_2, \dots, p_t(t⩽mnt \leqslant mn,各 pp 互不相同),满足:

  • p1∈Ep_1 \in E(第一步必须从边缘格取);
  • 对每个 k⩾2k \geqslant 2,要么 pkp_k 与 pk−1p_{k-1} 在方格中上下左右相邻,要么 pk−1∈Ep_{k-1} \in E 且 pk∈Ep_k \in E(前一步停在边缘时,可以"离开方格"再从任一未取的边缘格重新进入)。

一次取数只允许发生在这两种情况下;序列可以提前终止(取完所有数,或再也走不动、不想走),也就是说任何合法前缀都是一个合法的游戏过程。

得分规则:若 pkp_k 上的数是 jj,该次取数得 k×jk \times j 分。求 ∑k=1tk⋅apk\sum_{k=1}^{t} k \cdot a_{p_k} 的最大值。

注意"边缘 + 相邻"的连通性使序列并非任意排列。以样例 1 为例,答案是依次取 1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9 沿外围绕圈、最后取中心的顺序,得 1⋅1+2⋅2+⋯+9⋅9=2851\cdot 1 + 2\cdot 2 + \cdots + 9\cdot 9 = 285。

正解

思路

先想暴力:枚举所有取数序列并检查合法性。合法序列数量最坏到 16!16! 量级,显然不可行。但本题的两个自由度其实都很小,这正是可以状压的信号:

  • 走到哪了只取决于"哪些格子已经取走"和"当前站在哪一格"。已经取走的集合只有 216=655362^{16} = 65536 种,当前格只有 1616 种,状态总量 ⩽216×16≈2.1×106\leqslant 2^{16} \times 16 \approx 2.1 \times 10^6——完全在可承受范围内。
  • 得分的系数(第几次取)不受状态以外的东西影响:取走 k−1k-1 个格子后,下一个取走的数一定是第 kk 个,得分系数自动是 kk,不需要额外记录步数。

于是定义

dp[S][p]=已取走集合为 S、当前停在格 p 时的最大得分,dp[S][p] = \text{已取走集合为 } S \text{、当前停在格 } p \text{ 时的最大得分},

其中要求 p∈Sp \in S。先定初值:第一个数必须从边缘格入手,所以对每个 p∈Ep \in E 有 dp[{p}][p]=1⋅apdp[\{p\}][p] = 1 \cdot a_p。

转移时用刷表法(从已有状态推向更大集合)。设 k=∣S∣+1k = |S| + 1,则下一个取走的是第 kk 个数,从 pp 出发有两种合法走法:

  1. 走到相邻的未取格 qq:dp[S∪{q}][q]←max⁡(dp[S][p]+k⋅aq)dp[S \cup \{q\}][q] \leftarrow \max\big(dp[S][p] + k \cdot a_q\big);
  2. 离开方格再重新进入:仅当 pp 在边缘时可用,此时 qq 可以是任意未取的边缘格,同样是 dp[S∪{q}][q]←max⁡(dp[S][p]+k⋅aq)dp[S \cup \{q\}][q] \leftarrow \max\big(dp[S][p] + k \cdot a_q\big)。

两条规则是"或"的关系,写代码时可以把候选 qq 直接并到一个列表里统一松弛;也可以理解成在同一时刻只有"相邻"和"边缘跳转"两个入口,选其中更好的那个即可。注意 pp 在边缘时两条都可能成立,但 S∪{q}S \cup \{q\} 的规模一致,取最大值不会出错。

集合只增不减,所以按 SS 从小到大枚举就是天然的拓扑序:处理 dp[S][⋅]dp[S][\cdot] 时它的所有前驱集合大小都是 ∣S∣−1|S|-1、掩码更小,必然已被处理完。转移沿着"取数序列"逐步进行,第一次取数必在边缘这一约束已经写进初值,之后每一步都按题面规则产生,因此 dp[S][p]dp[S][p] 的每条转移都对应一个合法过程,最大得分不会超过真实最优;反过来,最优取数序列的每个前缀都对应状态中一条真实的转移路径(要么相邻、要么从边缘跳转),所以最优解一定能被枚举到。二者结合即得答案。

答案取所有 dp[S][p]dp[S][p] 的最大值(外带下界 00),因为游戏允许随时结束——取不动时结束,或者干脆一个数都不取,得 00 分。

下面用 2×22 \times 2 方格、a=(1234)a = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}(编号 0,10,1 是第一行、2,32,3 是第二行,四格全在边缘)展示状态表。行是集合 SS,列是当前格 pp,- 表示不可达:

SS(二进制,位 ii 表示格 ii 已取) p=0p=0 p=1p=1 p=2p=2 p=3p=3
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 行即取完四格的结果,dp=30dp = 30 对应路径 0→1→3→20 \to 1 \to 3 \to 2,即 1,2,4,31, 2, 4, 3 得 1⋅1+2⋅2+3⋅4+4⋅3=301\cdot1 + 2\cdot2 + 3\cdot4 + 4\cdot3 = 30。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

状态数 2mn⋅mn2^{mn} \cdot mn,每个状态 O(mn)O(mn) 次转移(相邻最多 44 个,边缘跳转最多 ∣E∣|E| 个),故时间复杂度 O(2mn⋅(mn)2)O(2^{mn} \cdot (mn)^2),空间复杂度 O(2mn⋅mn)O(2^{mn} \cdot mn)。取 mn=16mn = 16 时约 6.9×1076.9 \times 10^7 次转移,C++ 实测最大点 0.020.02 秒。Python 用稀疏字典存状态,最大点约 0.90.9 秒。

总结

本题的关键观察是:状态只需要"已取集合 ++ 当前格"两个维度,得分系数由 ∣S∣|S| 自动推出,不必记录步数。所有约束都能就地翻译成转移——第一步在边缘(写进初值)、相邻走(邻居表)、边缘跳转(额外入口)。集合规模单调递增保证了掩码从小到大枚举就是正确顺序;"游戏可随时结束"则翻译成对所有状态取最大、下界为 00。这是状压 DP 处理"路径或排列"类问题的标准套路:把"已经去过哪里"压成掩码,把"现在在哪里"当作掩码之外的那一维。