A34519. 闯关游戏问题描述你来到了一个闯关游戏。这个游戏总共有N关，每关都有M个通道，你需要选择一个通道并通往后续关卡。其中，第i个通道可以让你前进ai关，也就是说，如果你现在在第x关，那么选择第i个通道后，你将直接来到第x+ai关（特别地，如果 x+ai ≥N，那么你就通关了）。此外，当你顺利离开第8关时，你还将获得b8分。游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？输入描述第一行两个整数…
填空题
困难
知识点
题目描述
闯关游戏
问题描述
你来到了一个闯关游戏。
这个游戏总共有N关，每关都有M个通道，你需要选择一个通道并通往后续关卡。其中，第i个通道可以让你前进ai关，也就是说，如果你现在在第x关，那么选择第i个通道后，你将直接来到第x+ai关（特别地，如果 x+ai ≥N，那么你就通关了）。此外，当你顺利离开第8关时，你还将获得b8分。
游戏开始时，你在第0关。请问，你通关时最多能获得多少总分？
输入描述
第一行两个整数 N,M，分别表示关卡数量和每关的通道数量。
接下来一行M个用单个空格隔开的整数 a0.....am-1保证 1≤ai ≤N。
接下来一行N个用单个空格隔开的整数 b0.....bn-1。保证 |bi |≤100000。
输出描述
一行一个整数，表示你通关时最多能够获得的分数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入1
6 2
2 3
1 0 30 100 30 30
样例输出1
131
样例解释1
你可以在第0关选择第1个通道，获得1分并来到第3关；随后再选择第0个通道，获得 100分并来到第5关；最后任选一个通道，都可以获得30分并通关。如此，总得分为 1+100+30=131。
样例输入2
6 2
2 3
1 0 30 100 30 -1
样例输出2
101
样例解释2
请注意，一些关卡的得分可能是负数。
数据规模
对于20%的测试点，保证M=1。
对于40%的测试点，保证N≤20；保证M≤2。
对于所有测试点，保证N≤10000；保证M≤100。
参考答案
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 10005;
const int M = 105;
const int inf = 0x3f3f3f3f;
int a[M], b[N], f[N];
int main() {
// freopen("data/1.in", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i ++)
scanf("%d", &b[i]);
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i < n; i ++)
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]]);
int ans = -inf;
for (int i = 0; i < n; i ++)
for (int j = 1; j <= m; j ++)
if (i + a[j] >= n) {
ans = max(ans, f[i] + b[i]);
break ;
}
cout << ans << endl;
return 0;
}
上一题
下一题