OI题库

问题描述

农夫约翰的奶牛喜欢玩硬币游戏，因此约翰设计了一种新的双人对弈硬币游戏Xoinc。
开始，在地上有N (5 <= N <= 2,000)个硬币堆成的一个栈，硬币i有一个整数值C_i (1 <= C_i <= 100,000)

第一个玩家（先手玩家）可以从硬币栈的顶部开始取一个或两个硬币(C_1 and maybe C_2) 。如果第一个玩家取走了栈顶的一个硬币，第二个玩家（后手玩家）在下一步可以取走一个或两个硬币。如果第一个玩家取走了栈顶的两个硬币，第二个玩家可以取走1，2，3或4个硬币。在每一步，当前玩家至少取一个，最多取对手两倍数量的硬币。

然后，他们用得到的硬币价值宴请约翰，所以他们都想在游戏中获得最大价值的硬币。傲慢的后手玩家说我将使用最理想的策略取得胜利，那么先手玩家如何才能在游戏结束时得到最大价值的硬币。

输入格式

第1行：一个整数N
第2--N+1行：第i+1行有一个整数表示C_i

输入样例：(xoinc.in):

5
1
3
1
7
2

输入解释：有5个硬币价值分别为1,3,1,7和2

输出格式

一行：一个整数表示先手玩家能获得的最大硬币价值

输出样例：(xoinc.out):

9
输出解释：先手玩家开始取了一个硬币（价值1）。对手取了一个硬币（价值3）.先手玩家又取了两个硬币（价值1,7,总数为9）。后手玩家得到了剩余的硬币（价值2，总数为5）

数据规模:

对于20%的数据,5<=N<=10
对于30%的数据,5<=N<=100
对于50%的数据,5<=N<=500
对于100%的数据,5<=N<=2000