← 返回题目列表

Codeforces · 729/F

F. 金融家游戏

中文机器翻译题面 查看原题

此问题存在异常的内存限制。

晚上,金融家伊戈尔和热尼亚觉得无聊,所以他们决定玩一个游戏。他们用某公司一段时期的收入准备了n篇论文。请注意,收入可以为正、零或负。

伊戈尔和热尼亚将纸片排成一排,决定轮流下棋。伊戈尔将从左侧拿走文件,热尼亚将从右侧拿走文件。伊戈尔先走,从左边拿走 1 或 2 张(根据他的选择)试卷。然后,如果对手在上一回合中恰好拿走了 k 张纸,则在每个回合中,玩家可以从自己这边拿走 k 或 k + 1 张纸。玩家不能跳过动作。当没有剩余纸片或某些玩家无法采取行动时,游戏结束。

你的任务是确定 Igor 拿走的纸上的收入总和与 Zenya 拿走的纸上的收入总和之间的差异,假设两名玩家都发挥最佳。伊戈尔想要最大化差异,热尼亚想要最小化它。

输入

第一行包含单个正整数 n (1 ≤ n ≤ 4000) — 论文数量。

第二行包含 n 个整数 a1, a2, ..., an ( - 105 ≤ ai ≤ 105),其中 ai 是左起第 i 张纸上的收入。

输出

假设两名玩家都发挥最佳状态,打印 Igor 拿走的纸上的收入总和与 Zenya 拿走的纸上的收入总和之间的差额。伊戈尔想要最大化差异,热尼亚想要最小化它。

示例

输入 #1

3
1 3 1

输出 #1

4

输入 #2

5
-1 -2 -1 -2 -1

输出 #2

0

输入 #3

4
-4 -2 4 5

输出 #3

-13

注意

在第一个例子中,伊戈尔从左边拿走两张纸,使收入之和等于 4 是有利可图的。然后,Zhenya 将无法采取行动,因为只有一张纸,他只能拿 2 或 3 张。