GESP 题解库 / 6 级题解 / [GESP202312 六级] 闯关游戏 · 第 20 / 27 题
GESP202312 六级 · P10108 · 简单

闯关游戏

每关选一个通道前进若干关,离开时得分,求通关最高总分。

📊
N ≤ 10⁴, M ≤ 100
数据规模
🔢
int
分数范围
⚡
O(NM)
时间复杂度
🎯
倒序 DP(从终点往前推)
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

共 N 关(编号 0 ~ N−1),每关有 M 个通道,第 i 个通道可以前进 aᵢ 关(若 x + aᵢ ≥ N 则通关)。顺利离开第 s 关时获得 bₛ 分(可为负)。从第 0 关开始,求通关时的最高总分。

💡
人话翻译:典型的"从终点往回推"的 DP。
设 f[v] = "从第 v 关开始、最终通关能拿到的最高分"。那么 f[v] = b_v + maxᵢ f[v + aᵢ],其中 越界(v + aᵢ ≥ N)时 f = 0。
因为 v + aᵢ > v,所以从 N−1 往 0 倒着递推即可,答案就是 f[0]。

🔍 关键词提取

倒序 DP状态定义越界处理负数得分

已知条件

项目说明
输入第一行 N、M;第二行 M 个 aᵢ;第三行 N 个 bᵢ
输出最高总分
数据范围1 ≤ N ≤ 10⁴,1 ≤ M ≤ 100
分数范围|bᵢ| ≤ 10⁵(可为负)
通关条件位置 ≥ N

需要解决的问题

02
思维导图
整理解题思路的全貌
🚀 f[v] = b_v + max f[v + a_i]
🧠 状态
f[v]:从第 v 关开始的最高总分
答案 = f[0]
倒序计算(从 N−1 到 0)
规模 O(N)
📐 转移
枚举 M 个通道
f[v] = b_v + max f[v + aᵢ]
越界时该通道的 f 取 0
取所有通道的最大值
⚠️ 负数处理
bᵢ 可能为负
所以不能"能拿就拿"
必须比较所有通道
越界项 0 是"通关即停"
⚠️ 易错点
正序递推(依赖关系反了)
越界项当成负无穷或跳过
f 数组开小导致越界
用 int 忘了和可能较小但类型仍应够用
03
样例手算推导
两个样例的完整推演

🧮 样例 1:N = 6,M = 2,a = [2, 3],b = [1, 0, 30, 100, 30, 30]

从最后一关开始往前推。f[v] = b_v + max(f[v+2], f[v+3])。

1
v = 5(最后一关)

两个通道都越界(5 + 2 = 7 ≥ 6,5 + 3 = 8 ≥ 6)

max 项都是 0

f[5] = b₅ + 0 = 30

f[5] = 30

2
v = 4

两个通道同样越界

f[4] = b₄ + 0 = 30

f[4] = 30

3
v = 3

通道 a=2 → 走到第 5 关 → f[5] = 30

通道 a=3 → 走到第 6 关 → 越界 → 0

f[3] = b₃ + max(30, 0) = 100 + 30 = 130

f[3] = 130

4
v = 2

a=2 → f[4] = 30;a=3 → f[5] = 30

f[2] = 30 + 30 = 60

f[2] = 60

5
v = 1

a=2 → f[3] = 130;a=3 → f[4] = 30

f[1] = 0 + max(130, 30) = 130

f[1] = 130

6
v = 0

a=2 → f[2] = 60;a=3 → f[3] = 130

f[0] = 1 + max(60, 130) = 131

✅ f[0] = 131

vb_vf[v+2]f[v+3]f[v]
530越界 0越界 030
430越界 0越界 030
310030越界 0130
230303060
1013030130
0160130131

答案 131 ✓ 与样例解释的路径(0 → 3 → 5 → 通关)一致

🔑
对照样例解释验证:0 关选 a=3 → 到第 3 关(得 1 分);3 关选 a=2 → 到第 5 关(得 100 分);5 关任选 → 通关(得 30 分)。总分 1 + 100 + 30 = 131 ✓。
我们的 f 值也正好是这条路径的和,说明状态设计正确。

🧮 样例 2:把最后的 30 改成 −1

只有 b₅ 从 30 变成 −1,结果却从 131 变成 101——这说明"负分关卡要尽量跳过"。

vb_vf[v+2]f[v+3]f[v]
5−100−1
4300030
3100−10100
23030−160
1010030100
0160100101
1
关键在 v = 3

a=2 → 到第 5 关,那段只能拿 −1 分

a=3 → 直接越界通关,拿 0 分

所以要选 a=3,避免踩到负分关

f[3] = 100 + max(−1, 0) = 100

f[3] = 100(而不是 99)

2
连锁影响

f[1] 原本用 f[3] = 130,现在用 100

f[0] = 1 + max(f[2], f[3]) = 1 + max(60, 100) = 101

比样例 1 少了 29(正好是 −1 与 30 的差 31?)

实际差是 131 − 101 = 30

✅ 答案 101

⚠️
这个对比非常重要:负分关卡的存在意味着不能贪心地"尽量往前走"——有时提前通关反而更优。
DP 的 max 恰好处理了这种取舍:它在"继续走"和"直接通关"之间选更划算的。而越界项取 0(而不是负无穷)正是"通关即停不扣分"的体现。
04
解法对比
倒序 DP vs 贪心一路向前

⚔️ 解法对比

🟢 倒序 DP(推荐) 推荐

f[v] = b_v + max f[v + aᵢ],从 N−1 推到 0

  • 时间 O(NM) = 10⁶
  • N = 10⁴、M = 100 时轻松通过
  • 代码 15 行
  • 空间 O(N)
💡
转移式的直觉:f[v] 表示"站在第 v 关时的最优前景",等于"这一关的分"加上"跳到下一关后的最优前景"。越界时下一关的前景是 0(已通关)。

🟠 贪心:每关都选最远的通道

总选 a 最大的通道,尽快通关

  • 看起来"少走几关更好"
  • 但忽略了 b 值
  • 样例 1 会错(选远处可能跳过 100 分)
  • 无正确性保证
⚠️
为什么贪心不行:如果第 3 关有 100 分,而"选最远通道"会跳过它,那贪心就亏了。得分与路径长度并无单调关系,所以必须 DP。

📈 性能对比

方案复杂度正确性
倒序 DPO(NM)✅ 最优
贪心选最远O(N)❌ 有反例
05
算法流程图
从最后一关倒推到第 0 关
开始读入 N、M、数组 a、数组 b;f[N..N+M] 全部置 0v 从 N − 1 递减到 0best = 0(这是"直接通关"的前景)遍历 M 个通道 aᵢv + aᵢ 是否小于 N?是 ✓best = max(best, f[v + aᵢ])否 ✗该通道直接通关,前景为 0f[v] = b[v] + best输出 f[0]试下一个通道
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🚀 通关最高总分

第一行输入 N 和 M,第二行输入各通道前进关卡数,第三行输入各关得分。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int a[105], b[10005];
long long f[10005 + 105];      // 多开一些,方便越界取 0

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) scanf("%d", &a[i]);
    for (int i = 0; i < N; i++) scanf("%d", &b[i]);

    // 从最后一关倒推到第 0 关
    for (int v = N - 1; v >= 0; v--) {
        long long best = 0;                 // 直接通关:后续前景为 0
        for (int i = 0; i < M; i++) {
            int nxt = v + a[i];
            if (nxt < N) best = max(best, f[nxt]);
            // nxt >= N 表示这一步就通关,前景 0,不影响 max
        }
        f[v] = b[v] + best;
    }

    printf("%lld\n", f[0]);
    return 0;
}
🔑
为什么 best 初值取 0?因为"选择某个通道后如果越界就直接通关",通关之后不再扣分也不加分,所以那一条路的前景就是 0。
把 best 初值设为 0,相当于默认"至少可以直接通关拿 0 分",再与各个通道比较取更优。这与"倒序递推 + 越界取 0"是两种等价的写法。

📖 关键几行怎么看

代码作用为什么这样写
f 数组开大一点越界保护避免 f[v + aᵢ] 越界访问
for (v = N−1; v >= 0; v--)倒序f[v] 依赖更大的下标
long long best = 0初值直接通关的前景是 0
if (nxt < N)越界判断只有没通关才需要看后续
f[v] = b[v] + best转移本关得分 + 后续最优前景
⚠️
四个坑:① 正序递推(依赖关系反了,结果全错);② best 初值取负无穷而不是 0(会漏掉"直接通关"这条路);③ 忘记判断 nxt < N 导致数组越界;④ 用 int 存累加和(N × |b| 可达 10⁹ 量级,建议 long long)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6 2
2 3
1 0 30 100 30 30
131题面样例 1
6 2
2 3
1 0 30 100 30 -1
101题面样例 2(末尾为负分,提前通关更优)
1 1
1
5
5只有一关,选通道即通关
3 1
1
-1 -2 -3
-6只能一路向前:(−1) + (−2) + (−3) = −6
3 2
1 3
10 10 10
30f[1]=20,故 f[0]=10+20=30(跳过第 2 关更划算)
✅
自查清单:① 倒序推吗?② best 初值是 0 吗?③ 判了越界吗?

🚨 易错点清单

⚠️
正序递推:f[v] 依赖 f[v + aᵢ],必须倒着推。
⚠️
best 初值取负无穷:应取 0(代表"直接通关")。
⚠️
数组越界:注意先判断 v + aᵢ < N。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(NM)
空间复杂度
O(N + M)
N, M 最大
10⁴ × 100
运算量
约 10⁶

时间怎么算的?

空间都用在哪?

需要存 a、b 和 f 数组。

✅ 约 100 万次操作,瞬间完成。本题的难点在"想到倒着推"以及"越界项取 0"这两个细节。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 倒序 DP 的适用特征
// 1. 状态 v 只能"前进"到 v + a_i(不能后退)
// 2. 问的是"从起点出发能获得的最优值"
// 3. 边界在"越界/终点"处,且边界值容易确定
// -> 从后往前推

// 通用骨架
for (int v = N - 1; v >= 0; v--) {
    long long best = 终止值;          // 直接结束时的收益
    for (每个后继 nxt)
        if (合法(nxt)) best = max(best, f[nxt]);
    f[v] = 本步收益 + best;
}
// 答案 = f[起点]

// 与"正序 DP"的区别
// 正序:f[v] 表示"到达 v 时的最优值",转移 f[v] -> f[v + a]
// 倒序:f[v] 表示"从 v 出发的最优值",转移由后继回推
// 两种写法等价,但"倒序"往往更容易处理"终点"和"越界"

// 类似题目
// - 跳格子最大得分
// - 树上从叶子往根的最优值
// - 有向无环图上的最长/最短路径

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
倒序 DP从终点往起点推跳跃类、有向无环图上的最优路径
越界取 0直接结束的收益所有"走到边界即结束"的 DP
负数得分必须比较所有后继不能贪心,必须 DP
🌟
思考题:如果题目改成"必须恰好走 K 关才能通关",DP 要怎么改?(提示:需要增加一维"已经走了几关",即 f[v][k]。"附加约束"往往会带来"状态维度增加",这也是 DP 题难度上升的主要来源。)