#F3. 跳格子

跳格子

T3 跳格子(jump)

时间限制:1.0 秒 空间限制:256 MB

题目描述

地面上从左到右排着 nn 个格子,编号为 1,2,…,n1, 2, \dots, n。第 ii 个格子上写有一个整数价值 viv_i,价值可能为负。

你从格子 11 出发,想要恰好停在格子 nn。每一步你可以向前跳恰好 11 格、22 格或 33 格,但有两个限制:

  • 跳跃后不能越过格子 nn(即落点编号不超过 nn);
  • 不能连续两次跳相同的格数(第一次跳跃没有此限制)。

你的得分为所有落点(包括起点格子 11 与终点格子 nn)上的价值之和。注意:被跳过的格子不计入得分。

请你求出最大可能的得分。可以证明,总能通过若干次跳跃恰好停在格子 nn。

输入格式

第一行一个正整数 nn。

第二行 nn 个整数 v1,v2,…,vnv_1, v_2, \dots, v_n。

输出格式

输出一行一个整数,表示最大得分。

样例 1

输入:

5
3 2 10 1 4

输出:

10

样例 1 解释: 最优方案为 1→2→4→51 \to 2 \to 4 \to 5(依次跳 11、22、11 格),得分为 3+2+1+4=103 + 2 + 1 + 4 = 10。其他方案:1→2→51 \to 2 \to 5(跳 11、33 格)得 99;1→4→51 \to 4 \to 5(跳 33、11 格)得 88。虽然格子 3 的价值高达 1010,但不能去:跳 22 格到格子 3 后,下一步只能跳 11 或 33 格(到格子 4 或 6),到格子 4 后下一步只能跳 22 或 33 格,都会越过终点——到达格子 3 后就无法恰好停在格子 5 了。而 1→3→51 \to 3 \to 5(连续两跳 2 格)、1→3→4→51 \to 3 \to 4 \to 5(后两跳都是 1 格)也都违规。

样例 2

输入:

3
5 100 1

输出:

6

样例 2 解释: 从格子 1 出发,若先跳 1 格到格子 2,下一步只能跳 2 或 3 格,会越过格子 3,无法恰好停在终点;因此唯一方案是直接从格子 1 跳 2 格到格子 3,得分 5+1=65 + 1 = 6。格子 2 上高达 100 的价值是拿不到的!

数据范围

对于全部测试数据:1≤n≤1051 \le n \le 10^5;−109≤vi≤109-10^9 \le v_i \le 10^9。

注意: 得分可能很大(超过 32 位整数的表示范围),请使用 64 位整数。