BZOJ 2101: [Usaco2010 Dec]Treasure Chest 藏宝箱（这是我写过最骚气的dp！）
题目描述
贝西和邦妮找到了一个藏宝箱，里面都是金币！但是身为两头牛，她们不能到商店里把金币换成好吃的东西，于是她们只能用这些金币来玩游戏了。
藏宝箱里一共有N枚金币，第i枚金币的价值是Ci。贝西和邦妮把金币排成一条直线，她们轮流取金币，看谁取到的钱最多。贝西先取，每次只能取一枚金币，而且只能选择取直线两头的金币，不能取走中间的金币。
当所有金币取完之后，游戏就结束了。 贝西和邦妮都是非常聪明的，她们会采用最好的办法让自己取到的金币最多。
请帮助贝西计算一下，她能拿到多少钱？
输入
第1行：单个整数N，表示硬币的数量，1<=N≤5000第2~N+1行：第i+1行有一个整数Ci，代表第i块硬币的价值，1≤Ci≤5000
输出
输出一行：单个整数，表示如果双方都按最优策略玩游戏，先手可以拿到的最大价值。样例输入 传送门 ←
↗ ↑ ↖
（完）