简答题 偏难
#21617

闯关游戏 时间限制:1.0 s 内存限制:128.0 MB 问题描述 你来到了一个闯关游戏。 这个游戏总共有N关,每关都有M个通道,你需要选择一个通道并通往后续…

闯关游戏

时间限制:1.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

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≤104;保证M≤100。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;string&gt; 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", &amp;n, &amp;m);   for (int i = 1; i &lt;= m; i++)     scanf("%d", &amp;a[i]);   for (int i = 0; i &lt; n; i++)     scanf("%d", &amp;b[i]);   memset(f, -0x3f, sizeof(f));   f[0] = 0;   for (int i = 1; i &lt; n; i++)     for (int j = 1; j &lt;= m; j++)       if (i - a[j] &gt;= 0)         f[i] = max(f[i], f[i - a[j]] + b[i - a[j]]);   int ans = -inf;   for (int i = 0; i &lt; n; i++)     for (int j = 1; j &lt;= m; j++)       if (i + a[j] &gt;= n) {         ans = max(ans, f[i] + b[i]);         break;       }   cout &lt;&lt; ans &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。