P3004 [USACO10DEC] Treasure Chest S

Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins. The N (1

输入的第一行是一个整数 $n$，代表硬币的个数。 第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。

输出一行一个整数，代表小 A 能获得的最大累计价值。

#### 输入输出样例 $1$ 解释 初始时，硬币序列为 $\{30,~25,~10,~35\}$。 第一回合，小 A 取走最右侧的硬币，序列变为 $\{30,~25,~10\}$，小 A 的累加价值为 $35$。 第二回合，小 B 取走最左侧的硬币，序列变为 $\{25,~10\}$，小 B 的累加价值为 $30$。 第三回合，小 A 取走最左侧的硬币，序列变为 $\{10\}$，小 A 的累加价值为 $35 + 25 = 60$。 第四回合，小 B 取走最左侧的硬币，序列变为空，小 B 的累加价值为 $30 + 10 = 40$，游戏结束。 小 A 获得的最大累计价值为 $60$。 #### 数据范围与约定 对于全部的测试点，$1 \leq n \leq 5 \times 10^3$，$1 \leq c_i \leq 5 \times 10^3$。 **提示：请注意，本题的空间限制为 $64$ Mib。**