形式化题目

棋盘是一排 $N$ 个格子，第 $i$ 格的分数为 $a_i$（$a_i \geqslant 0$）。乌龟从第 $1$ 格出发（自动获得 $a_1$），手上有 $M$ 张卡片，每张标有 $1,2,3,4$ 之一：打出一张标 $k$ 的卡片，乌龟就向前走 $k$ 格，每张卡片恰好用一次。

用光全部 $M$ 张卡片后，乌龟恰好落在第 $N$ 格；途中到达的每个格子都计一次分数。求一种出牌顺序，使经过格子的分数总和最大。

样例解释

样例中 $N=9$，卡片为 1 3 1 2 1（三张 1、一张 2、一张 3），最优顺序 1,1,3,1,2 的行走路线是：

合计 $6+10+14+8+18+17=73$。注意第 4、5 格被跳过，不得分；同一个格子被"经过"（跳过）不算到达。

正解

思路

朴素做法及其瓶颈。 最直接的枚举是给 $M$ 张卡片排出一个全排列，逐个模拟算分——但 $M \leqslant 120$ 时排列数高达 $120!$，完全不可行。注意到同数字的卡片互相没有区别：真正影响得分轨迹的只有"每类数字各打了几张"，而不是打牌的具体顺序。设四类卡片张数为 $c_1,c_2,c_3,c_4$，用牌总数为 $S = c_1+c_2+c_3+c_4$，则乌龟此刻恰好站在第 $1 + (c_1 + 2c_2 + 3c_3 + 4c_4)$ 格——位置被用牌组合唯一确定，不需要在状态里单独存。也就是说，值得考虑的"局面"最多只有 $41^4 \approx 2.8 \times 10^6$ 个。

从枚举顺序到计数 DP。 进一步观察：某个组合 $(c_1,c_2,c_3,c_4)$ 的最大得分，与到达它之前"最后打的是哪张牌"有关，而最后一张牌只能是 $1/2/3/4$ 四种之一，且打完它之后的组合是确定的（对应数字的计数减一）。这就给了自然的递推结构：

其中 $f(0,0,0,0) = a_1$（起点的分数自动获得）。这里"计数即状态、每类减一即转移"的结构与背包 DP 同源：四种数字相当于四种"体积"，只是它们共同拼出的是前缀位置而非一个背包容量。下图展示样例中从起点出发、用一张 1 的两种路径分岔——同样的用牌组合，走的轨迹可以不同，但DP按组合记账后只保留最大值：

flowchart LR
    S["(0,0,0,0) 格1 得6"] -->|"打1→格2"| A["(1,0,0,0) 得16"]
    S -->|"打2→格3"| B["(0,1,0,0) 得20"]
    A -->|"打2→格4"| C["(1,1,0,0) 得22"]
    B -->|"打1→格4"| C

从 (1,0,0,0) 打 2、和从 (0,1,0,0) 打 1，都会到达组合 (1,1,0,0)，但得分不同（$22$ 与 $18$）——这正是 DP 取 max 的意义，也说明得分依赖路径顺序，而组合本身不依赖，所以必须把"每个组合的最优值"存下来。

实现方式。 既可以用四维数组 f[c1][c2][c3][c4] 按 $S$ 从小到大递推，也可以用记忆化搜索。下面的代码采用另一种等价写法：用 dict 以四元组为键直接从 $(0,0,0,0)$ 前向推——枚举每个可达组合，尝试再打一张数字 $k$ 的卡片，把 cnt[k] 加一后得到的新组合的得分用 max 更新。这样状态里只存"实际可达"的组合，且无需写显式的四层逆序循环。需要注意两处剪枝：某类卡片用完就不能再打该类；下一步若走出棋盘（新位置 $> N$）则这条出牌不合法。题目保证用光 $M$ 张牌恰好落在终点，所以答案就是"四类牌全部用完"的那个状态。

代码

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/**
 * 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 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; if (!(cin >> n >> m)) return 0;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int cnt[5] = {0, 0, 0, 0, 0};
    for (int i = 0; i < m; i++) { int x; cin >> x; cnt[x]++; }
    static ll dp[45][45][45][45];
    static bool ok[45][45][45][45];
    ok[0][0][0][0] = true; dp[0][0][0][0] = a[0];
    for (int c1 = 0; c1 <= cnt[1]; c1++)
    for (int c2 = 0; c2 <= cnt[2]; c2++)
    for (int c3 = 0; c3 <= cnt[3]; c3++)
    for (int c4 = 0; c4 <= cnt[4]; c4++) {
        if (!ok[c1][c2][c3][c4]) continue;
        int pos = c1 + 2 * c2 + 3 * c3 + 4 * c4;
        int cs[5] = {0, c1, c2, c3, c4};
        for (int k = 1; k <= 4; k++) {
            if (cs[k] == cnt[k] || pos + k >= n) continue;
            int n1 = c1, n2 = c2, n3 = c3, n4 = c4;
            if (k == 1) n1++; else if (k == 2) n2++; else if (k == 3) n3++; else n4++;
            ll gain = dp[c1][c2][c3][c4] + a[pos + k];
            if (!ok[n1][n2][n3][n4] || gain > dp[n1][n2][n3][n4]) {
                ok[n1][n2][n3][n4] = true; dp[n1][n2][n3][n4] = gain;
            }
        }
    }
    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << '\n';
    return 0;
}

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#!/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-02 09:05
# update_at: 2026-10-02 09:05

import sys
from itertools import product


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    a = [next(data) for _ in range(n)]  # a[i]：第 i+1 格的分数（0 起下标）

    cnt = [0] * 5  # cnt[k]：数字为 k 的卡片张数，cnt[0] 不用
    for _ in range(m):
        cnt[next(data)] += 1

    # dp[(c1,c2,c3,c4)]：四类卡片分别用了 c1..c4 张时的最大得分。
    # 用牌总数唯一决定当前位置（第 1 格 + 已走步数），所以状态里不必再存位置。
    # 题目保证用光 M 张牌恰好到终点，答案就是四类牌全部用完时的状态值。
    dp = {(0, 0, 0, 0): a[0]}  # 起点：还没出牌，已自动获得第 1 格分数
    for c1, c2, c3, c4 in product(range(cnt[1] + 1), range(cnt[2] + 1),
                                  range(cnt[3] + 1), range(cnt[4] + 1)):
        state = (c1, c2, c3, c4)
        cur = dp.get(state)
        if cur is None:
            continue  # 这个用牌组合从起点走不到
        pos = c1 + 2 * c2 + 3 * c3 + 4 * c4  # 已走步数 = 当前格子的 0 起下标
        for k in range(1, 5):
            nxt_pos = pos + k
            if state[k - 1] == cnt[k] or nxt_pos >= n:
                continue  # 数字 k 的牌已用完，或这一步会跳出棋盘
            nxt = state[:k - 1] + (state[k - 1] + 1,) + state[k:]
            gain = cur + a[nxt_pos]
            if gain > dp.get(nxt, -1):
                dp[nxt] = gain

    print(dp[(cnt[1], cnt[2], cnt[3], cnt[4])])


if __name__ == "__main__":
    solve()

复杂度

状态数是 $\prod_{k=1}^{4}(c_k+1) \leqslant 41^4 \approx 2.8 \times 10^6$，每个状态最多 $4$ 次转移，总时间 $O(c_1 c_2 c_3 c_4)$（约 $10^7$ 级别）；空间同样是 $O(c_1 c_2 c_3 c_4)$。这与 C++ 正解同阶。

总结

• 同类物品无区别时，“排列枚举"应压缩为"计数组合”：本题的关键观察是用牌总数唯一决定乌龟位置，从而把状态从「位置 + 剩余所有牌」砍成四维计数。
• 转移是"最后一动画牌"的逆推（或等价的前向扩展），每个状态最多 $4$ 个前驱/后继，这是计数 DP 的典型形态。
• 用 dict + 元组状态可以省掉四维数组的边界书写，代价是常数变大；Python 实现需留意 nxt_pos < n 与"该类牌是否用完"两个合法性检查。
• 得分依赖行走顺序、状态却与顺序无关，二者靠 max 融合——凡是"过程有序、结果只看计数"的题都可以套用这个框架。

图示解析

下图把样例的 DP 状态按"已用牌数 $S$"分层，每层列出组合、对应格子与最大得分（- 表示该组合不可达，格子数 = $1 + c_1 + 2c_2 + 3c_3$，本题没有数字 4 的牌）：

观察重点：

• 每一层的状态只从上一层转移而来（每打一张牌 $S$ 加一），所以按 $S$ 递增处理即是无后效性的拓扑序。
• 最优出牌顺序 1,1,3,1,2 对应链 (0,0,0)→(1,0,0)→(2,0,0)→(2,0,1)→(3,0,1)→(3,1,1)，逐状态得分 $6,16,30,38,56,73$；例如 (1,1,0) 得 $22$ 是从 (0,1,0) 打 1 到达的（$20+2$），比从 (1,0,0) 打 2 到达的 $18$ 更优，体现取 max 的必要性。
• 终态 (3,1,1) 的 $73$ 正是样例答案，且它由 (3,0,1)（打 2）转移而来，与题面给出的最优出牌顺序一致。