G6003 [GESP202312 六级] 闯关游戏 题解

知识点：动态规划、有向无环状态、负权处理。

解题思路

令dp[i]为从关卡i出发能取得的最大总分，从后向前计算dp[i]=b[i]+max(dp[min(n,i+x)])，x遍历允许跳跃距离。

为什么正确

所有后继都在当前位置之后，逆序时已得到最优值；枚举第一跳并加当前分数覆盖全部可行路线。

易错点

分数可能为负，枚举后继的临时最大值不能初始化为0；超过终点统一映射终止状态。

复杂度

时间O(nm)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(m),b(n);
    for(int &x:a)cin>>x;
    for(int &x:b)cin>>x;
    vector<long long>dp(n+1);
    for(int i=n-1;i>=0;i--) {
        long long best=LLONG_MIN;
        for(int x:a)best=max(best,dp[min(n,i+x)]);
        dp[i]=b[i]+best;
    }
    cout<<dp[0];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。