硬币游戏

硬币游戏

题目描述

农夫约翰的奶牛喜欢玩硬币游戏,因此他发明了一种称为“Xoinc”的两人硬币游戏。 初始时,一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上,从堆顶数起的第I枚硬币的币值为C_i (1 <= C_i <= 100,000)。 开始玩游戏时,第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币,那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币,则第二个玩家可以拿走1,2,3,或4枚硬币。在每一轮中,当前的玩家至少拿走一枚硬币,至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时,游戏结束。 两个玩家都希望拿到最多钱数的硬币。请问,当游戏结束时,第一个玩家最多能拿多少钱呢?

输入格式

第1行:1个整数N
第2..N+1行:第i+1行包含1个整数C_i

输出格式

第1行:1个整数表示第1个玩家能拿走的最大钱数。

样例输入

5
1
3
1
7
2

样例输出

9

提示

样例说明:第1个玩家先取走第1枚,第2个玩家取第2枚;第1个取走第3,4两枚,第2个玩家取走最后1枚。
Silver

信息

难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者