12969.闯关游戏

题目分析

我们面对的是一个有向无环图（DAG）上的最长路问题，或者更具体地说，是一个一维动态规划问题。

• 共有 $N$ 关，编号 $0 \sim N-1$，初始在第 $0$ 关。
• 每关有 $M$ 个通道，第 $i$ 个通道可以让你前进 $a_i$ 关。
• 离开第 $s$ 关时会获得 $b_s$ 分（$b_s$ 可能为负数）。
• 一旦当前关卡编号 $x$ 满足 $x + a_i \ge N$，即视为通关，游戏结束并获得离开当前关的分数。
• 目标：最大化从开始到通关的总得分。

数据范围：$N \le 10^4$，$M \le 100$，$|b_i| \le 10^5$。

解题思路

状态定义

设 f[i] 表示到达第 $i$ 关时，已经获得的最大总分。这里的“到达”指的是刚刚通过某些通道到达第 $i$ 关，并且尚未加上离开第 $i$ 关的得分 $b_i$。

• 起始状态：游戏开始时我们在第 $0$ 关，还没有获得任何分数，因此 f[0] = 0。
• 对于无法到达的关卡，f[i] 应初始化为一个很小的负数。

状态转移

对于第 $i$ 关（$1\le i<N$），我们可以从更靠前的某一关 $k$ 通过某个通道 $j$ 到达，即 $k + a_j = i$，所以 $k = i - a_j$。
在离开第 $k$ 关时我们会获得 $b_k$ 分，因此：

注意，转移只依赖于编号比 $i$ 小的关卡，因此我们可以按关卡编号从小到大依次计算。

计算最终答案

当我们到达某关 $i$（$0\le i<N$）后，如果存在一个通道 $j$ 使得 $i + a_j \ge N$，说明从当前关可以直接通关。通关时我们还能获得离开第 $i$ 关的得分 $b_i$，因此总分为 f[i] + b[i]。

最终答案即为所有可行通关方案得分的最大值：

算法说明

1. 读入 $N, M$，以及数组 $a$（通道前进量）和 $b$（每关离开得分）。
2. 初始化 f 数组为负无穷（例如 -0x3f3f3f3f），设 f[0] = 0。
3. 从 $i = 1$ 到 $N-1$，遍历所有通道 $j = 1 \sim M$：
   • 若 $i - a_j \ge 0$，则 f[i] = max(f[i], f[i - a_j] + b[i - a_j])。
4. 初始化答案 ans 为负无穷。
5. 遍历所有关卡 $i = 0 \sim N-1$，遍历所有通道 $j = 1 \sim M$：
   • 若 $i + a_j \ge N$，则用 f[i] + b[i] 更新 ans。
6. 输出 ans。

时间复杂度分析

• 状态数：$O(N)$。
• 每个状态转移需要枚举所有通道，$O(M)$。
• 总时间复杂度 $O(N \times M)$，在 $N \le 10^4$，$M \le 100$ 时约为 $10^6$，完全可以在一秒内运行完毕。
• 空间复杂度 $O(N + M)$，主要存储 f、a、b 数组。

参考代码及解释

cpp
复制
1#include <cstdio>
2#include <cstdlib>
3#include <cstring>
4#include <algorithm>
5#include <iostream>
6using namespace std;
7
8const int N = 10005;
9const int M = 105;
10const int inf = 0x3f3f3f3f;
11int a[M], b[N], f[N];
12
13int main() {
14    int n, m;
15    scanf("%d%d", &n, &m);
16    // 读入每个通道的前进量
17    for (int i = 1; i <= m; ++i)
18        scanf("%d", &a[i]);
19    // 读入离开每关的得分
20    for (int i = 0; i < n; ++i)
21        scanf("%d", &b[i]);
22
23    // 初始化 f 为负无穷，表示尚未到达
24    memset(f, -0x3f, sizeof(f));
25    f[0] = 0;   // 初始在第0关，得分0
26
27    // DP：按关卡顺序递推
28    for (int i = 1; i < n; ++i) {
29        for (int j = 1; j <= m; ++j) {
30            if (i - a[j] >= 0) {
31                f[i] = max(f[i], f[i - a[j]] + b[i - a[j]]);
32            }
33        }
34    }
35
36    // 统计答案：从可以通关的关卡中选择最大得分
37    int ans = -inf;
38    for (int i = 0; i < n; ++i) {
39        for (int j = 1; j <= m; ++j) {
40            if (i + a[j] >= n) {
41                ans = max(ans, f[i] + b[i]);
42                break;  // 找到一个能通关的通道即可，无需继续枚举
43            }
44        }
45    }
46
47    cout << ans << endl;
48    return 0;
49}

代码细节说明

• 负无穷初始化：memset(f, -0x3f, sizeof(f)) 会将每个字节设为 0x3f，从而让 int 型变量变成非常小的负数，表示“无法到达”。同时也保证了在取 max 时不会被无效状态干扰。
• 转移顺序：i 从小到大枚举，保证了计算 f[i] 时所有 i - a_j 的结果已经求出，满足动态规划的无后效性。
• 最终答案：内层循环中一旦发现 i + a[j] >= n 就跳出，因为只需确认该关卡能否直接通关，不必继续浪费循环。
• 区间细节：$b$ 数组下标从 $0$ 到 $n-1$，对应关卡编号 $0 \sim N-1$。离开第 $i$ 关得 $b_i$，而通关时还会加上最后所在关的 $b_i$，代码中加了一次，即在 f[i] + b[i] 中体现。

总结

本题本质上是一个带有“通关跳跃”性质的简单动态规划问题。关键在于正确理解“到达”与“离开”得分之间的关系，将状态定义为到达第 $i$ 关的累计得分（不含离开 $i$ 的得分），最后特判通关条件并补充最后一份得分即可。由于数据范围不大，$O(NM)$ 的 DP 可以轻松通过所有测试点。