自动搬运

查看原文

来自洛谷，原作者为

	zsh_haha 当我发现当年的剪贴板失效了，当年的灌水区关停了，当年的洛谷氛围消失了，我终于明白了……OI不过是我成长的一站，我要换乘了||想想当年刚入坑OI，入坑洛谷时的稚嫩，也是现在美好的回忆，也只是一句感慨，一声叹息罢

搬运于2025-08-24 22:54:44，当前版本为作者最后更新于2024-01-28 23:37:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

让我们简化一下题目。

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

解题思路

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

我们设 $f_i$ 表示到达第 $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;
}