3280 - 轮流取数2

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 32 MB

小 A 和小 B 在玩游戏。

初始时，数组有 $n$ 个数从左到右摆放，从左至右第 $i$ 个数值为 $c_i$ 。

游戏的规则是，两人交替从数组的左侧连续取出若个数字，然后将取出的数值累加至自己获得的累计价值中。若对方上次操作取出了 $k$ 个数，那么本次自己最多取出 $k \times 2$ 个数。当没有数可取时，游戏结束。

游戏开始时，由小 A 先动手取数，最多取出 $2$ 个数。

请求出当双方都尽可能使自己的累计价值最大的情况下，小 A 能获得的累计价值最大是多少。

输入的第一行是一个整数 $n$ ，代表数组的长度。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数 $c_i$ ，表示数组每个数的值。

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

$5 \leq n \leq 2 \times 10^3$ ， $1 \leq c_i \leq 10^5$ 。

USACO