59 lines
1.9 KiB
C++
59 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 1e4 + 10;
|
||
const int INF = 0x3f3f3f3f;
|
||
int n, m; // n个关卡，每个关卡都有一样的m个通道
|
||
int a[N]; // 第i个通道可以让你前进a[i]关,,比如：现在第x关，选择i通道，将到达第x+a[i]关
|
||
int b[N]; // 当你离开第s关时，将获得b[s]分的奖励
|
||
int f[N]; // 动态规划数组，f[i]表示离开第i关时可以获得的最大分数
|
||
int ans = -INF; // 通关时最多能够获得的分数
|
||
|
||
/*
|
||
6 2
|
||
2 3
|
||
1 0 30 100 30 30
|
||
答案:131
|
||
|
||
|
||
6 2
|
||
2 3
|
||
1 0 30 100 30 -1
|
||
答案：101
|
||
*/
|
||
int main() {
|
||
cin >> n >> m; // 输入n和m
|
||
|
||
// 每一个关卡都有m个通道,a[i]表示第i个通道可以让你前进a[i]关
|
||
int mx = 0;
|
||
for (int i = 1; i <= m; i++) {
|
||
cin >> a[i];
|
||
mx = max(mx, a[i]);
|
||
}
|
||
|
||
for (int i = 0; i < n; i++) // 关卡是从下标0开始的
|
||
cin >> b[i]; // 通关i关时可以获得的奖励分数
|
||
// 动态规划
|
||
// 状态表示：f[i]表示通关第i关时可以获得的最大分数
|
||
// 状态转移：f[i] = max(f[i],f[i-a[j]]+b[i-a[j]])
|
||
// 初始化：f[0] = 0
|
||
// 答案：f[n]
|
||
|
||
// 因为得分可能是负数，所以初始化的时候，需要将f[i]初始化为-0x3f
|
||
memset(f, -0x3f, sizeof f);
|
||
f[0] = 0;
|
||
for (int i = 1; i < n + mx; i++) { // 遍历每个阶段
|
||
// 考虑当前阶段的所有决策，也就是到达这个阶段，可以有哪些决策
|
||
// 决策：选择第j个通道，那么到达这个阶段，可以获得的最大分数就是f[i-a[j]]+b[i-a[j]]
|
||
// 所以，f[i] = max(f[i],f[i-a[j]]+b[i-a[j]])
|
||
for (int j = 1; j <= m; j++) {
|
||
if (i - a[j] >= 0)
|
||
f[i] = max(f[i], f[i - a[j]] + b[i - a[j]]);
|
||
}
|
||
}
|
||
|
||
for (int i = n - 1; i < n + mx; i++)
|
||
ans = max(ans, f[i] + b[i]);
|
||
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |