P83280

轮流取数2

难度 6 级 初三 动态规划入门 线性 博弈
讨论 统计 4通过 8提交 50%通过率 旧版界面
时间限制 1 秒 内存限制 32 MB

题目描述

小 A 和小 B 在玩游戏。

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

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

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

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

输入

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

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

输出

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

样例

样例 1
输入
5 
1 
3 
1 
7 
2
输出
9

提示

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

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交