P10108 [GESP202312 六级] 闯关游戏

题目背景

题目链接：P10108 [GESP202312 六级] 闯关游戏 - 洛谷

对应的选择、判断题：https://ti.luogu.com.cn/problemset/1138

题目描述

你来到了一个闯关游戏。

这个游戏总共有 $N$ 关，每关都有 $M$ 个通道，你需要选择一个通道并通往后续关卡。其中，第 $i$ 个通道可以让你前进 $a_i$ 关，也就是说，如果你现在在第 $x$ 关，那么选择第 $i$ 个通道后，你将直接来到第 $x+a_i$ 关（特别地，如果 $x + a_i \geq N$，那么你就通关了）。此外，当你顺利离开第 $s$ 关时，你还将获得 $b_s$ 分。

游戏开始时，你在第 $0$ 关。请问，你通关时最多能获得多少总分。

输入格式

第一行两个整数 $N$，$M$，分别表示关卡数量和每关的通道数量。

接下来一行 $M$ 个用单个空格隔开的整数 $a_0,a_1\cdots,a_{M-1}$。保证 $1\le a_i \le N$。

接下来一行 $N$ 个用单个空格隔开的整数 $b_0,b_1\cdots,b_{N-1}$。保证 $|b_i|\le 10^5$。

输出格式

一行一个整数，表示你通关时最多能够获得的分数。

输入输出样例 #1

输入 #1

1
2
3
6 2 
2 3
1 0 30 100 30 30

输出 #1

1
131

输入输出样例 #2

输入 #2

1
2
3
6 2
2 3
1 0 30 100 30 -1

输出 #2

1
101

说明/提示

样例解释 1

你可以在第 $0$ 关选择第 $1$ 个通道，获得 $1$ 分并来到第 $3$ 关；随后再选择第 $0$ 个通道，获得 $100$ 分并来到第 $5$ 关；最后任选一个通道，都可以获得 $30$ 分并通关。如此，总得分为 $1+100+30=131$。

样例解释 2

请注意，一些关卡的得分可能是负数。

数据范围

对于 $20%$ 的测试点，保证 $M=1$。

对于 $40%$ 的测试点，保证 $N \le 20$；保证 $M\le 2$。

对于所有测试点，保证 $1 \le N \le 10^4$；保证 $1 \le M\le 100$。

题解

这道题的核心是动态规划，因为每一关的最优得分都依赖于后续关卡的最优得分，且存在重复子问题和最优子结构的特征。

核心思路

  1. 状态定义：设 dp[x] 表示从第 x 关出发，通关时能获得的最大总分。我们的目标是求 dp[0]（从第 0 关开始）。

  2. 状态转移：

    • 对于第 x 关，选择任意通道 i 会前进 a[i] 关，到达 x+a[i] 关。
    • 若 x+a[i] >= N，说明直接通关，此时从 x 关出发的得分就是 b[x]（离开第x关的得分）。
    • 若 x+a[i] < N，说明到达第 x+a[i] 关，此时得分是 b[x] + dp[x+a[i]]（当前关得分 + 后续关的最大得分）。
    • 因此状态转移方程为：dp[x] = max{ b[x] + (x+a[i]>=N ? 0 : dp[x+a[i]]) }（遍历所有M个通道取最大值）。

  3. 遍历顺序：由于第x关的dp值依赖于更大的 x的dp值，因此需要从后往前遍历关卡（从N-1到0）。

AC Code

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e4 + 10;
ll dp[N]; // 不开祖宗见long long

int main() {
    // 加速，防超时
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(n);
    for (int i = 0; i < m; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];

    // 从后往前遍历计算 dp[x]
    for (int x = n - 1; x >= 0; --x) {
        ll max_score = -INT_MAX; // 初始化最小值（防止 b[i] 为负数）
        for (int i = 0; i < m; ++i) {
            int next_x = x + a[i];
            ll cur;
            if (next_x >= n)
                cur = b[x]; // 直接通关
            else
                cur = b[x] + dp[next_x]; // 到下一关
            max_score = max(max_score, cur);
        }
        dp[x] = max_score;
    }

    cout << dp[0] << "\n"; // 从 0 关出发的最大得分
    return 0;
}