logo AlgoBeat OnlineJudge 返回比赛
登录 注册

B. [ABSEC0006] 你

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

“你”踏上了一条充满未知与挑战的修行之路。前方是长长的石阶,每一步都可能蕴含着天地灵气,也可能布满着煞气。

石阶共有 级,编号从 。“你”初始时站在编号为 的平地上,目标是到达编号为 的山顶。

“你”每一步可以选择向前跳跃 级、 级或 (即如果当前在 级,可以跳到 级)。

每一级石阶上都有一个能量值 。如果 为正,代表能吸收灵气;如果为负,代表煞气会损耗你的修为。平地 和山顶 的能量值均为

当你降落在一个石阶上时,你就会吸收(或损耗)对应的能量值。

请问,在到达山顶 的所有合法路径中,“你”能获得的最大能量值总和是多少?

输入格式

第一行包含一个整数 ()。

第二行包含 个整数 ()。

输出格式

输出一个整数,表示到达山顶能获得的最大能量值总和。

样例

【样例输入】

5
-2 4 -5 6 -3

【样例输出】

10

【样例说明】

最优跳跃路径为:

  • 0 跳 2 级到达 2,获得能量 4。当前总能量:4
  • 2 跳 2 级到达 4,获得能量 6。当前总能量:10
  • 4 跳 2 级到达 6(山顶),获得能量 0。当前总能量:10

这是所有合法方案中可获得能量的最大值。