乌龟棋

形式化题目

棋盘是 $N$ 个格子的序列，格子 $i$ 有权值 $a_i$ （保证非负）。棋子从格子 $1$ 出发，手里有写数字 $1,2,3,4$ 的卡片，写 $k$ 的卡片有 $c_k$ 张。每张卡片用且仅用一次，用写 $k$ 的卡片就向前移动 $k$ 格，经过（到达）的每个格子都取走它的权值，起点格子 $1$ 的权值必定计入。保证 $\sum_{k=1}^{4} k\,c_k = N-1$ ，即用光所有卡片时棋子恰好停在格子 $N$ 。

问：所有卡片使用顺序中，取走权值总和（含 $a_1$ ）的最大值是多少。

样例 $N=9$ ， $a=(6,10,14,2,8,8,18,5,17)$ ，卡片为 $1,3,1,2,1$ （即 $c_1=3,c_2=1,c_3=1,c_4=0$ ），答案为 $73$ ，一条最优路线是 $1 \to 2 \to 3 \to 6 \to 7 \to 9$ ：按 1,1,3,1,2 的顺序用卡，取走 $6+10+14+8+18+17=73$ 。

正解

思路

第一步：把"顺序"换成"计数"。

样例只有 5 张卡， $5!/3!=20$ 种顺序可以直接枚举；但 $M=120$ 时排列数是天文数字。观察顺序里真正的冗余：棋子的位置不是独立的状态量，它完全由"各类卡片各用掉几张"决定。设 $x_k$ 为写 $k$ 的卡片已经用掉的张数，则

\mathrm{pos}(x_1,x_2,x_3,x_4) = x_1 + 2x_2 + 3x_3 + 4x_4 .

两条不同的使用顺序，只要四类卡的使用张数相同，棋子就停在同一个格子、面对同一个子问题；而历史得分只影响"这条路好不好"，不影响"接下来有哪些选择"。这正是动态规划的封闭性。

第二步：写出转移。

用状态 $(x_1,x_2,x_3,x_4)$ 记录四类卡各用了几张， $\mathrm{dp}$ 表示到达该状态的最大得分。最后一张卡可以是四类中任意一类（只要那类还有剩余），而四类前驱的落点是同一个格子 $\mathrm{pos}(x)$ ，所以格子分 $a_{\mathrm{pos}+1}$ 是公共加项：

\mathrm{dp}(x)=\max_{k:\,x_k>0}\mathrm{dp}(x-e_k)+a_{\mathrm{pos}(x)+1},\qquad \mathrm{dp}(0,0,0,0)=a_1 .

朴素地按这四层循环填表，状态数 $S=\prod_{k=1}^{4}(c_k+1)$ 。在 $c_k \leqslant 40$ 、 $\sum_k c_k \leqslant 120$ 、 $\sum k\,c_k = N-1 \leqslant 349$ 的约束下， $S$ 最坏约 $31^4 \approx 9.2\times10^{5}$ ，本身可接受——复杂度上已经到位了，下面两步只是让 Python 在 1000 ms 内跑得动，并不改变复杂度。

第三步：把 $c_4$ 维压成一条链。

固定 $(c_1,c_2,c_3)$ 后看第 $c_4$ 维：其中三个前驱（少一张 1/2/3 卡）与它同处 $c_4$ ，只有"少一张 4 卡"落在本行左邻。于是上式可以重排成

\mathrm{dp}[c_4]=\underbrace{\max\Big(\max_{k=1,2,3}\mathrm{dp}[x-e_k][c_4],\ \mathrm{dp}[c_4-1]\Big)}_{\text{两种候选}}\;+\;a_{\mathrm{pos}+1}.

括号里第一项只跟当前列有关，可以先逐位取 max 得到 best；第二项是"本行左邻"，所以整行 $c_4=0,1,\dots,c_4^{\max}$ 是一条链式递推，用一次 itertools.accumulate 就能扫完，不必写第四层循环。

样例的完整状态表（格子写"得分 (落点编号)"，两个切片 $c_3=0$ 与 $c_3=1$ ，均取 $c_4=0$ ）：

已用 3 卡 $c_3$	已用 1 卡 $c_1$	$c_2=0$ 得分 (落点)	$c_2=1$ 得分 (落点)
0	0	6 (格子 1)	20 (格子 3)
0	1	16 (格子 2)	22 (格子 4)
0	2	30 (格子 3)	38 (格子 5)
0	3	32 (格子 4)	46 (格子 6)
1	0	8 (格子 4)	28 (格子 6)
1	1	24 (格子 5)	46 (格子 7)
1	2	38 (格子 6)	51 (格子 8)
1	3	56 (格子 7)	73 (格子 9)

表格由题目专用脚本 problem-analysis-workspace/viz_render.py 的教学版 DP 复算得到（这里 $c_4=0$ ，所以落点就是 $\mathrm{pos}=c_1+2c_2+3c_3$ ）。读表时看三点。第一，一个状态只比某个前驱多拿"新落的那一格"的分： $\mathrm{dp}(1,0,0)=6+a_2=16$ 、 $\mathrm{dp}(3,0,0)=30+a_4=32$ ，增量就是新格子的分，各不相同。第二，同一个格子可以由不同的用卡组合到达： $\mathrm{dp}(2,0,0)$ 与 $\mathrm{dp}(0,1,0)$ 落点都是格子 3，但得分分别是 30 和 20，所以必须保留更优的那一个——这正是"取 max"在做的事。第三，答案就是右下角 $\mathrm{dp}(3,1,1)$ ：它从三个前驱中取最大再加格子 9 的分，即 $\max(56,51,46)+a_9=\max(56,51,46)+17=73$ ，与样例一致。

以 $c_4$ 非零的真实数据（数据仓 input1.in： $N=13$ ，棋盘 32 37 75 16 64 33 79 97 22 2 99 100 41，卡片 4,2,2,4，即 $c_2=2,c_4=2$ ）为例， $c_1=c_3=0$ 的 $(c_2,c_4)$ 切片把"链"看得最清楚：

已用 2 卡 $c_2$ \ 已用 4 卡 $c_4$	0	1	2
0	32	96	118
1	107	186	285
2	171	208	326

同一行内每往右一格，就是"少用一张 4 卡"的前驱（本行左邻）与"少用一张 2 卡"的前驱（上一行同列）竞争，两者都停在同一个格子，所以格子分是公共加项；例如 $\mathrm{dp}(0,1,0,1)$ 的两条候选是 $\mathrm{dp}(0,0,0,1)=96$ (落点格子 5)和 $\mathrm{dp}(0,1,0,0)=107$ (落点格子 3)，都要加上格子 7 的 $a_7=79$ ，于是 $\max(96,107)+79=186$ 。第一行（ $c_2=0$ ）没有异维前驱，纯粹是沿 $c_4$ 向前的前缀和。

第四步： $c_1$ 维滚动。

平面内按 $c_2$ 、 $c_3$ 递增即可保证三个异维前驱先算好； $c_1$ 维只需保留上一层平面，于是空间从 $O(S)$ 降到 $O(c_2^{\max}\cdot c_3^{\max}\cdot c_4^{\max})$ 。对应到代码：dp_row 负责一行 $c_4$ 的全部转移，solve 只做读入、三维调度和输出。

代码

dp_row(prev_1, prev_2, prev_3, gains, seed) 回答"固定 $c_1,c_2,c_3$ 后，整行 $c_4$ 是多少"：三个异维前驱逐位 map(max) 得到 best，再与格子分打包交给 accumulate，回调 max(acc, p[0]) + p[1] 就是 $\max(\text{本行左邻},\ \text{三个异维前驱}) + a_{\mathrm{pos}+1}$ 。 solve 里 step = c1 + 2*c2 + 3*c3 是 $c_4=0$ 时的落点， board[step : step + 4*n4 + 1 : 4] 一次取出本行全部格子分； dead_row 是某类卡已用完时的整行哨兵，让 max 自动忽略不存在的方向。

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/**
 * 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-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 乌龟棋：状态只记四类卡片各用了几张
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 400;

ll board[MAXN];        // board[i]：第 i+1 个格子的分数
ll cnt[5];             // cnt[k]：写着数字 k 的卡片张数
// dp[c1 维奇偶][c2][c3][c4]：四类卡各用了这么多张时能得到的最大得分
ll dp[2][42][42][42];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &board[i]);
    }
    for (int i = 0; i < m; i++) {
        int b;
        scanf("%d", &b);
        cnt[b]++;
    }

    int n1 = cnt[1], n2 = cnt[2], n3 = cnt[3], n4 = cnt[4];
    const ll NEG = -(1LL << 50); // 不可达状态哨兵，远低于任何真实得分

    for (int c1 = 0; c1 <= n1; c1++) {
        int cur = c1 & 1, pre = (c1 - 1) & 1; // c1 维滚动，只留上一层平面
        for (int c2 = 0; c2 <= n2; c2++) {
            for (int c3 = 0; c3 <= n3; c3++) {
                for (int c4 = 0; c4 <= n4; c4++) {
                    int pos = c1 + 2 * c2 + 3 * c3 + 4 * c4; // 四元组唯一确定落点
                    if (pos == 0) {
                        dp[cur][0][0][0] = board[0]; // 起点：自动获得第 1 格的分数
                        continue;
                    }
                    ll best = NEG;
                    if (c1 > 0) best = max(best, dp[pre][c2][c3][c4]);      // 最后一手用 1 卡
                    if (c2 > 0) best = max(best, dp[cur][c2 - 1][c3][c4]);  // 最后一手用 2 卡
                    if (c3 > 0) best = max(best, dp[cur][c2][c3 - 1][c4]);  // 最后一手用 3 卡
                    if (c4 > 0) best = max(best, dp[cur][c2][c3][c4 - 1]);  // 最后一手用 4 卡
                    dp[cur][c2][c3][c4] = best + board[pos]; // 四类前驱同处一格，格子分是公共加项
                }
            }
        }
    }

    printf("%lld\n", dp[n1 & 1][n2][n3][n4]); // 用光全部卡片，落点必是第 n 格
    return 0;
}

python

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#!/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-01 21:58
# update_at: 2026-10-01 22:06

import sys
from itertools import accumulate

# 不可达状态的哨兵：真实得分 ≥ 0，而它沿一条链最多被加 41 次、每次至多 100 分，
# 远不足以翻正，所以在 max 比较里永远输给任何真实结果。
NEG = -10**9


def dp_row(prev_1: list[int], prev_2: list[int], prev_3: list[int], gains: list[int], seed: int) -> list[int]:
    """固定已用 1/2/3 卡的张数，推出「用 c4 张 4 卡」整行的最大得分。

    下标 c4 表示 4 卡用了 c4 张。同一状态无论最后用的是哪类卡，都停在同一个格子
    step = c1 + 2*c2 + 3*c3 + 4*c4，所以格子分是该状态的公共加项：
    - best 是分别少用一张 1/2/3 卡的三行在同一 c4 上的逐位 max；
    - 少用一张 4 卡的前驱就是本行的前一格，是沿 c4 串起来的链；
    - 因此 dp[c4] = max(best[c4], dp[c4-1]) + gains[c4]，用 accumulate 一次扫完；
    - seed 是虚拟前驱的分数：起点那一行给 0（起点分数在 gains[0] 里再加一次），
      其余行给 NEG。NEG 只需足够深（见模块级注释）。
    """
    best = map(max, prev_1, prev_2, prev_3)  # 三类卡分别作为最后一手
    row = accumulate(zip(best, gains), lambda acc, p: max(acc, p[0]) + p[1], initial=seed)
    return list(row)[1:]  # 丢掉 initial 多出来的那一项


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    board = [next(data) for _ in range(n)]

    counts = [0] * 5  # counts[v] = 写着数字 v 的卡片张数（1..4）
    for _ in range(m):
        counts[next(data)] += 1
    n1, n2, n3, n4 = counts[1:]

    dead_row = [NEG] * (n4 + 1)  # 某类卡已用完时，该方向的前驱行整行不可达
    prev_plane: list[list[list[int]]] | None = None  # dp 的 c1-1 平面，逐层滚动，省内存
    for c1 in range(n1 + 1):
        plane: list[list[list[int]]] = []
        for c2 in range(n2 + 1):
            line: list[list[int]] = []
            for c3 in range(n3 + 1):
                step = c1 + 2 * c2 + 3 * c3  # 已走格子数，也就是当前格的下标
                gains = board[step : step + 4 * n4 + 1 : 4]  # 本行各 c4 落到的格子分
                prev_a = prev_plane[c2][c3] if c1 else dead_row
                prev_b = plane[c2 - 1][c3] if c2 else dead_row
                prev_c = line[c3 - 1] if c3 else dead_row
                seed = 0 if step == 0 else NEG  # 只有起点 (0,0,0,c4) 有 0 分的虚拟前驱
                line.append(dp_row(prev_a, prev_b, prev_c, gains, seed))
            plane.append(line)
        prev_plane = plane

    print(prev_plane[n2][n3][n4])  # 用光全部卡片，落点必是第 n 格


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O\!\left(\prod_{k=1}^{4}(c_k+1)\right)$ ，即状态数 $S$ ；每个状态均摊 $O(1)$ 。最坏约 $31^4 \approx 9.2\times10^{5}$ 个状态（不能取到 $41^4$ ，因为 $\sum_k c_k \leqslant 120$ 与 $\sum k\,c_k = N-1$ 同时限制）。
空间复杂度： $O(c_2^{\max}\cdot c_3^{\max}\cdot c_4^{\max})$ ，只保留 $c_1-1$ 的一个平面。
实测：真实数据 10 组全部通过，最慢 input10（ $N=292$ 、 $M=120$ ）0.112 s，峰值内存 16.8 MB（限制 1000 ms / 128 MB）；自造极端形状 $c_1=c_2=c_3=c_4=30$ （ $N=301$ ）0.118 s，峰值 18.2 MB。

总结

从"枚举卡片顺序"到"四维格路"只差一步观察：棋子的位置由四类卡的使用张数唯一决定，顺序里没有额外信息，于是状态只需 $(x_1,x_2,x_3,x_4)$ ，转移是"最后一手用了哪类卡"。四类前驱落在同一格子，所以格子分是公共加项；把 $c_4$ 维单列后它变成一条链，用一次前缀递推（accumulate）扫完， $c_1$ 维再滚动一层，就把四维表压到一维行 + 一个平面。复杂度仍是状态数级别 $O\!\left(\prod(c_k+1)\right)$ ，与标准 C++ 四维 DP 同阶。

两个容易踩的坑：一是贪心不成立——样例里每步挑“下一步分最大”的卡会得到 $68 < 73$ ，因为局部最大会被后续格子分布反噬；二是哨兵要足够负——用 NEG 表示不可达状态后，它沿一条链最多被加 41 次、每次至多 100 分（即至多 4100 分），必须保证仍为负，否则会盖过真实得分。

图示解析

这张图串起本题从卡片顺序到最终答案的推理链：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14输入：N 个格子的分数 + M 张卡片(1..4)
   |
   v
关键观察：棋子的位置只由「四类卡各用掉几张」决定
   |        pos(x) = x1 + 2*x2 + 3*x3 + 4*x4   -> 顺序信息冗余
   v
四维格路 DP：dp(x) = max_{k:x_k>0} dp(x-e_k) + a[pos+1]
   |        四类前驱落在同一格 -> 格子分是公共加项
   |        固定 (c1,c2,c3) 后，c4 维是一条链
   v
行内压缩：best = max(三个异维前驱) ; 本行 = accumulate(best, gains)
   |        c1 维滚动，只留上一层平面
   v
答案 dp(c1,c2,c3,c4)   O(prod(c_k+1)) 时间、O(c2*c3*c4) 空间

顺着箭头看：第一步把"排列"降维成"计数"，第二、三步把四层循环压成"三维循环 + 一次链式扫描"，最后按 $c_1$ 滚动省掉整个四维表。图中每个节点都对应正文中的一条结论，不涉及样例的具体数值。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析