每关选一个通道前进若干关,离开时得分,求通关最高总分。
共 N 关(编号 0 ~ N−1),每关有 M 个通道,第 i 个通道可以前进 aᵢ 关(若 x + aᵢ ≥ N 则通关)。顺利离开第 s 关时获得 bₛ 分(可为负)。从第 0 关开始,求通关时的最高总分。
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 |
f[v]:从第 v 关出发能获得的最高总分f[v] 依赖 f[v + aᵢ](更大的下标),所以按 v 从大到小计算v + aᵢ ≥ N 表示这一步就通关了,之后没有关卡可走,所以那一项取 0从最后一关开始往前推。f[v] = b_v + max(f[v+2], f[v+3])。
两个通道都越界(5 + 2 = 7 ≥ 6,5 + 3 = 8 ≥ 6)
max 项都是 0
f[5] = b₅ + 0 = 30
f[5] = 30
两个通道同样越界
f[4] = b₄ + 0 = 30
f[4] = 30
通道 a=2 → 走到第 5 关 → f[5] = 30
通道 a=3 → 走到第 6 关 → 越界 → 0
f[3] = b₃ + max(30, 0) = 100 + 30 = 130
f[3] = 130
a=2 → f[4] = 30;a=3 → f[5] = 30
f[2] = 30 + 30 = 60
f[2] = 60
a=2 → f[3] = 130;a=3 → f[4] = 30
f[1] = 0 + max(130, 30) = 130
f[1] = 130
a=2 → f[2] = 60;a=3 → f[3] = 130
f[0] = 1 + max(60, 130) = 131
✅ f[0] = 131
| v | b_v | f[v+2] | f[v+3] | f[v] |
|---|---|---|---|---|
| 5 | 30 | 越界 0 | 越界 0 | 30 |
| 4 | 30 | 越界 0 | 越界 0 | 30 |
| 3 | 100 | 30 | 越界 0 | 130 |
| 2 | 30 | 30 | 30 | 60 |
| 1 | 0 | 130 | 30 | 130 |
| 0 | 1 | 60 | 130 | 131 |
答案 131 ✓ 与样例解释的路径(0 → 3 → 5 → 通关)一致
1 + 100 + 30 = 131 ✓。只有 b₅ 从 30 变成 −1,结果却从 131 变成 101——这说明"负分关卡要尽量跳过"。
| v | b_v | f[v+2] | f[v+3] | f[v] |
|---|---|---|---|---|
| 5 | −1 | 0 | 0 | −1 |
| 4 | 30 | 0 | 0 | 30 |
| 3 | 100 | −1 | 0 | 100 |
| 2 | 30 | 30 | −1 | 60 |
| 1 | 0 | 100 | 30 | 100 |
| 0 | 1 | 60 | 100 | 101 |
a=2 → 到第 5 关,那段只能拿 −1 分
a=3 → 直接越界通关,拿 0 分
所以要选 a=3,避免踩到负分关
f[3] = 100 + max(−1, 0) = 100
f[3] = 100(而不是 99)
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
max 恰好处理了这种取舍:它在"继续走"和"直接通关"之间选更划算的。而越界项取 0(而不是负无穷)正是"通关即停不扣分"的体现。f[v] = b_v + max f[v + aᵢ],从 N−1 推到 0
f[v] 表示"站在第 v 关时的最优前景",等于"这一关的分"加上"跳到下一关后的最优前景"。越界时下一关的前景是 0(已通关)。总选 a 最大的通道,尽快通关
| 方案 | 复杂度 | 正确性 |
|---|---|---|
| 倒序 DP | O(NM) | ✅ 最优 |
| 贪心选最远 | O(N) | ❌ 有反例 |
第一行输入 N 和 M,第二行输入各通道前进关卡数,第三行输入各关得分。
点按钮开始 →
#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)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 2 | 131 | 题面样例 1 |
6 2 | 101 | 题面样例 2(末尾为负分,提前通关更优) |
1 1 | 5 | 只有一关,选通道即通关 |
3 1 | -6 | 只能一路向前:(−1) + (−2) + (−3) = −6 |
3 2 | 30 | f[1]=20,故 f[0]=10+20=30(跳过第 2 关更划算) |
f[v] 依赖 f[v + aᵢ],必须倒着推。v + aᵢ < N。需要存 a、b 和 f 数组。
✅ 约 100 万次操作,瞬间完成。本题的难点在"想到倒着推"以及"越界项取 0"这两个细节。
// 倒序 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 |
f[v][k]。"附加约束"往往会带来"状态维度增加",这也是 DP 题难度上升的主要来源。)