Problem
蚱蜢跳到位于同一直线上且彼此距离相等的柱子上。这些列的序列号从 1
到 N
。一开始,Grasshopper 坐在编号为 1
的柱子上。它可以从 1
向前跳到 K
柱,从当前柱开始计数。
在每一列上,蚱蜢可以获得或失去几个金币(这个数字对于每一列都是已知的)。确定 Grasshopper 需要如何跳跃才能收集到最多的金币。请记住,Grasshopper 不能向后跳。
输入:
- 第一行包含两个自然数:N
和 K
(\(2 <= N ,\ K <; = 10000\)), 空格分隔;
- 第二行,空格分隔的N-2
整数– Grasshopper 从第 2 到 N-1
每一列获得的硬币数量。如果这个数字是负数,Grasshopper 会失去硬币。
保证所有取模的数不超过10000。
输出:
- 在第一行,程序应该显示 Grasshopper 可以收集的最大硬币数量;
- 第二行显示Grasshopper的跳跃次数;
- 在第三行– Grasshopper 访问的所有列的数量(按升序由空格分隔)。
如果有几个正确答案,打印其中一个。
例子
<头>
<日>#日>
输入 |
输出 |
东西>
<正文>
1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|
表>