GESP六级题解：洛谷P10108闯关游戏动态规划解法详解

一、题目解读

本文针对2023年GESP六级题目“闯关游戏”（洛谷P10108）进行详细解析。题目要求玩家通过不同关卡路径选择，计算从起点到终点的最大得分。关卡间存在跳跃规则，需结合动态规划思想设计高效算法，最终输出最优得分。

二、解题思路

采用动态规划（Dynamic Programming）策略。核心思路为：

1. 逆向求解：从终点反向推算每关的最大得分，避免路径重复计算。

2. 状态定义：dp[i]表示从第i关到终点的最大得分，边界条件dp[N]=0（终点得分为0）。

3. 状态转移：遍历每关可选跳跃步数a[i]，计算下一关得分dp[next] + 当前关得分b[i]，取最大值更新dp[x]。

三、解题步骤拆解

1. 输入与初始化：读入关卡数N、跳跃规则数M，存储跳跃步数a[]与关卡得分b[]。

2. 动态规划核心逻辑：

从N-1关开始逆向循环，避免依赖后续状态。

遍历每个跳跃规则，计算可达下一关索引next。

若next关得分已计算（dp[next]有效），更新当前dp[x]为max(dp[next] + b[x])。

3. 输出结果：最终dp[0]即为起点到终点的最大得分。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(nullptr);
    
    int N, M; // N：关卡数，M：跳跃规则数
    cin >> N >> M;
    vector<int> a(M), b(N); // a[]存储跳跃步数，b[]存储关卡得分
    for (int i = 0; i < M; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];
    
    vector<int> dp(N + 1, -1e9); // dp[i]：从第i关到终点的最大得分
    dp[N] = 0; // 终点得分初始化为0
    
    // 逆向动态规划
    for (int x = N - 1; x >= 0; --x) {
        int max_score = -1e9; // 临时存储当前关最大得分
        for (int i = 0; i < M; ++i) {
            int next = min(x + a[i], N); // 计算跳跃后可达的下一关（不越界）
            if (dp[next]!= -1e9) { // 若下一关得分已计算
                max_score = max(max_score, dp[next] + b[x]); // 更新当前得分
            }
        }
        dp[x] = max_score; // 更新状态
    }
    
    cout << dp[0] << endl; // 输出起点到终点的最大得分
    return 0;
}

五、总结

本文通过动态规划解法，高效解决了GESP六级“闯关游戏”题目。逆向计算与状态压缩避免了重复计算，适用于存在路径依赖关系的优化问题。掌握此类算法思维，可提升对复杂路径规划类题目的解题能力。