题解

题目要求到从第 $1$ 个格子跳到第 $n$ 个格子所能获得的最大分数，每次跳跃的距离必须是一个斐波那契数。

非常经典的一类 DP 题目了，定义 $dp[i]$表示跳到第 $i$ 个格子所能获得的最大分数。

显然，$dp[0] = w[0]$

• 对于$dp[i] (i > 0)$，可以枚举上一步跳跃的距离 $val$，如果 $val$ 是一个斐波那契数，并且 $i - val >= 0$，那么可以从第 $i - val$ 个格子跳到第 $i$ 个格子，此时获得的分数为 $dp[i - val] + w[i]$

题目描述

小红小时候很喜欢一个叫跳格子的游戏，地上总共有$n$几个格子，小红跳到第$i$个格子可以获得$a_i$的分数。 小红从第1个格子开始，小红每次可以跳跃一个悲波那契数的长度，她想知道她恰好跳到第$n$个格子最多可以获得多少分。 所谓斐波那契数，指斐波那契数列:1,1,2,3,5,8.….中的某一项。悲波那契数列满足，第三项开始，每一项等于前两项之和。

输入描述

第一行输入一个整数$n(1\le n \le 2\times 10^5)$表示数组长度。

第二行输入$n$个整数表示每个格子的分数$a_i(-10^9\le a_i\le 10^9)$

输出描述

输出一个整数表示答案:

样例1

输入

3
1 2 3

输出

6

说明

第1步，跳跃1格，跳到第2个格子
第2步，跳跃1格，跳到第3个格子。
获得的分数为6。

样例2

输入

3
1 -2 3

输出

4