#F3. 跳格子
跳格子
T3 跳格子(jump)
时间限制:1.0 秒 空间限制:256 MB
题目描述
地面上从左到右排着 个格子,编号为 。第 个格子上写有一个整数价值 ,价值可能为负。
你从格子 出发,想要恰好停在格子 。每一步你可以向前跳恰好 格、 格或 格,但有两个限制:
- 跳跃后不能越过格子 (即落点编号不超过 );
- 不能连续两次跳相同的格数(第一次跳跃没有此限制)。
你的得分为所有落点(包括起点格子 与终点格子 )上的价值之和。注意:被跳过的格子不计入得分。
请你求出最大可能的得分。可以证明,总能通过若干次跳跃恰好停在格子 。
输入格式
第一行一个正整数 。
第二行 个整数 。
输出格式
输出一行一个整数,表示最大得分。
样例 1
输入:
5
3 2 10 1 4
输出:
10
样例 1 解释: 最优方案为 (依次跳 、、 格),得分为 。其他方案:(跳 、 格)得 ;(跳 、 格)得 。虽然格子 3 的价值高达 ,但不能去:跳 格到格子 3 后,下一步只能跳 或 格(到格子 4 或 6),到格子 4 后下一步只能跳 或 格,都会越过终点——到达格子 3 后就无法恰好停在格子 5 了。而 (连续两跳 2 格)、(后两跳都是 1 格)也都违规。
样例 2
输入:
3
5 100 1
输出:
6
样例 2 解释: 从格子 1 出发,若先跳 1 格到格子 2,下一步只能跳 2 或 3 格,会越过格子 3,无法恰好停在终点;因此唯一方案是直接从格子 1 跳 2 格到格子 3,得分 。格子 2 上高达 100 的价值是拿不到的!
数据范围
对于全部测试数据:;。
注意: 得分可能很大(超过 32 位整数的表示范围),请使用 64 位整数。