CCF-GESP计算机学会等级考试2023年12月六级C++T1闯关游戏

解析：递推，时间复杂度O(MN)，详见代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[10005];//到第i关获得的最高得分
int a[105];
int b[10005];
int ans = 0;
int main() {ios::sync_with_stdio(false);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; i++) {for(int j = 0; j < m; j++) {int t = min(i + a[j], n); //通关就算第n关if(dp[t]==0){dp[t] = dp[i] + b[i]; //考虑有负值的情况}else{dp[t] = max(dp[t], dp[i] + b[i]); //取最大值}}}cout << dp[n];return 0;
}