洛谷 P10108 [GESP202312 六级] 闯关游戏 题解
传送门
动态规划。注意，一些关卡的得分可能是负数。
AC Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[105],b[10005],c[10005];
int ans=-1e9;
int n,m;
int fun(int q){
if(q>=n) return 0;
if(c[q]!=-1e9){
return c[q];
}
for(int i=0;i<m;i++){
c[q]=max(c[q],b[q]+fun(q+a[i]));
}
return c[q];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a[i];
}for(int i=0;i<n;i++){
cin>>b[i];
c[i]=-1e9;
}
cout<<fun(0);
return 0;
}