时间限制: 2s
内存限制: 192MB 提交: 60 解决: 35
题目描述
最初地面上有一堆n个硬币(5< =n< =2000)，从上面数第i个硬币的价值为C_i(1< =C_i< =100000);
游戏开始后，A先取一枚或两枚硬币。如果A取了一枚，那么B可以继续取一枚或两枚；如果A取了两枚，那么B可以取一到四枚硬币。每次都只能从最上面取。每一次，当前取硬币的人都至少取一枚硬币，最多可以取他的对手上一次取硬币数目的两倍。当没有硬币可取的时候，游戏就结束了。
然后，他们就可以用得到的硬币向John买东西，当然，他们游戏的目的就是要尽可能使自己得到的硬币价值更大。现在你的任务是，求出在两个人都想得到更大价值的情况下，游戏结束后，第一个人最多能得到的硬币价值。
输入格式
第1行： 一个整数，N（5< =N< =2000）。
第2到n+1行： 第 i+1 行代表从上数第i枚硬币的价值。
输出格式
一行：一个数字，第一个人能得到的最大价值