1932: 硬币游戏
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：5
题目描述
工作之余，Daddy Squirrel 也经常会玩一些电脑游戏，当然，肯定不是CS、SC、WOW之类的。他比较喜欢玩的是一种和电脑对战的硬币游戏。游戏的规则很简单，有N枚硬币，每枚硬币都有面值，将这些硬币随机排成一行，然后 Daddy Squirrel 和电脑轮流取硬币，每次只允许取走第一枚或最后一枚硬币，当所有的硬币都被取走后，取走硬币总面值最大的那个就是胜者。由于电脑永远都会选择最优策略，因此，为了公平起见，总是由 Daddy Squirrel 首先开始取硬币。
比如，总共有四枚硬币，其面值依次为：30 25 10 35，如下的游戏顺序保证 Daddy Squirrel 可以取得最大的面值。
|
玩家 |
策略 |
面值 |
DS总面值 |
电脑总面值 |
剩余硬币 |
|
DS |
尾 |
35 |
35 |
0 |
30 25 10 |
|
电脑 |
首 |
30 |
35 |
30 |
25 10 |
|
DS |
首 |
25 |
60 |
30 |
10 |
|
电脑 |
首 |
10 |
60 |
40 |
―― |
现请你编程帮助 Daddy Squirrel 计算一下，如何才能保证其取得最大面值。
输入
输入数据共两行，第一行包含一个整数N（1<=N<=5,000），表示硬币的总数。
第二行，包含N个用空格隔开的整数，表示N枚硬币的面值。所有面值之和不超过长整型范围。
输出
输出数据仅一个整数，表示 Daddy Squirrel 所能取得的最大面值数。
样例输入 复制
4
30 25 10 35
样例输出 复制
60