简答题
偏难
#19105
闯关游戏 时间限制:2.0 s 内存限制:128.0 MB 问题描述 你来到了一个闯关游戏。 这个游戏总共有N关,每关都有M个通道,你需要选择一个通道并通往后续…
闯关游戏
时间限制:2.0 s
内存限制:128.0 MB
问题描述
你来到了一个闯关游戏。
这个游戏总共有N关,每关都有M个通道,你需要选择一个通道并通往后续关卡。其中,第i个通道可以让你前进ai关,也就是说,如果你现在在第x关,那么选择第i个通道后,你将直接来到第x+ai关(特别地,如果x+ai≥N,那么你就通关了)。此外,当你顺利离开第s关时,你还将获得bs分。
游戏开始时,你在第0关。请问,你通关时最多能获得多少总分?
输入描述
第一行两个整数N,M,分别表示关卡数量和每关的通道数量。
接下来一行M个用单个空格隔开的整数a0,a1,……,aM-1。保证1≤ai≤N。
接下来一行N个用单个空格隔开的整数b0,b1,……,bN-1。保证|bi|≤105。
输出描述
一行一个整数,表示你通关时最多能够获得的分数。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
你可以在第0关选择第1个通道,获得1分并来到第3关;随后再选择第0个通道,获得100分并来到第5关;最后任选一个通道,都可以获得30分并通关。如此,总得分为1+100+30=131。
样例输入 2
样例输出 2
样例解释 2
请注意,一些关卡的得分可能是负数。
数据规模
对于20%的测试点,保证M=1。
对于40%的测试点,保证N≤20;保证M≤2。
对于所有测试点,保证N≤104;保证M≤100。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n, m = input().split()
n, m = int(n), int(m)
a = list(map(int, input().split()))
b = list(map(int, input().split()))
max_b = max(a)
f = [b[0]]
ans = - 10 ** 18
for i in range(1, n):
f.append(None)
for step in a:
if i - step >= 0 and f[i - step] is not None:
f[i] = max(f[i], f[i - step]) if f[i] is not None else f[i - step]
if f[i] is not None:
f[i] += b[i]
if f[i] is not None and i + max_b >= n:
ans = max(ans, f[i])
print(ans)</pre>
这道题暂未补解析。