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

· · 题解

题目大意

让我们简化一下题目。

一共有 N 个关卡，从第 0 关开始，每次都可以往前跳 a_i 关，其中 0\le i< M。当你到达第 j 关时，你的得分必须加 b_i 分，其中 0\le j<N。

解题思路

我们可以用动态规划来解决这道题。

我们设 f_i 表示到达第 i 关时获得的分数的最大值。

不难看出，状态转移方程就是：

f_j=\max\{f_j,f_{j-a_i}+b_{j-a_i}\}

但这样就好了嘛？并没有，我们仔细看题目中的一句话：

特别地，如果 x+a_i\ge N，那么你就通关了。

没错，这里是 x+a_i\ge N，而不是 x+a_i=N 或 x+a_i=N-1。

所以 f 数组应该多算一点，防止有些最大值是在关卡外产生的。（重点）

值得注意的是，由于本题中 b_i 可能为负数，所以 f 数组要初始化为负无穷，而 f_0 也要记得初始化为 0。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int a[101],b[20001]/*b 数组多开是因为在算 f 数组时的需要*/;
int f[20001];//多算一点，算到 N+max{ai}=2N
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    for(int i=0;i<n+n;i++){
        f[i]=-1e9;//初始化为负无穷
    }
    f[0]=0;//记得 f[0] 要初始化为 0
    for(int j=0;j<n+n;j++){
        for(int i=0;i<m;i++){
            if(j>=a[i]){
                f[j]=max(f[j],f[j-a[i]]+b[j-a[i]]);
            }
        }
    }
    int ans=-1e9;//答案变量也要初始化为负无穷
    for(int i=n;i<n+n;i++){
        ans=max(ans,f[i]);//注意不能直接输出 f[n] 或 f[n-1]
    }
    cout<<ans;
    return 0;
}