AT_dp_l Deque

题目描述

太郎君和次郎君进行如下游戏。

最初，给定一个数列 $a = (a_1, a_2, \ldots, a_N)$。两人轮流进行如下操作，直到 $a$ 变为空。太郎君先手。

• 可以移除 $a$ 的首元素或末元素。设移除的元素为 $x$，则执行操作的人获得 $x$ 分。

游戏结束时，太郎君的总得分为 $X$，次郎君的总得分为 $Y$。太郎君希望最大化 $X - Y$，次郎君则希望最小化 $X - Y$。

假设两人都采取最优策略，求 $X - Y$ 的值。

输入格式

输入以如下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

假设两人都采取最优策略，输出 $X - Y$ 的值。

输入输出样例 #1

输入 #1

4
10 80 90 30

输出 #1

10

输入输出样例 #2

输入 #2

3
10 100 10

输出 #2

-80

输入输出样例 #3

输入 #3

1
10

输出 #3

10

输入输出样例 #4

输入 #4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

输出 #4

4999999995

输入输出样例 #5

输入 #5

6
4 2 9 7 1 5

输出 #5

2

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 3000$
• $1 \leq a_i \leq 10^9$

样例解释 1

两人采取最优策略时，操作过程如下。被操作的元素用粗体表示。

• 先手：（10, 80, 90, 30）→（10, 80, 90）
• 后手：（10, 80, 90）→（10, 80）
• 先手：（10, 80）→（10）
• 后手：（10）→（） 此时，$X = 30 + 80 = 110$，$Y = 90 + 10 = 100$。

样例解释 2

两人采取最优策略时，操作过程例如如下。

• 先手：（10, 100, 10）→（100, 10）
• 后手：（100, 10）→（10）
• 先手：（10）→（） 此时，$X = 10 + 10 = 20$，$Y = 100$。

样例解释 4

答案可能超出 32 位整数范围。

样例解释 5

两人采取最优策略时，操作过程例如如下。

• 先手：（4, 2, 9, 7, 1, 5）→（4, 2, 9, 7, 1）
• 后手：（4, 2, 9, 7, 1）→（2, 9, 7, 1）
• 先手：（2, 9, 7, 1）→（2, 9, 7）
• 后手：（2, 9, 7）→（2, 9）
• 先手：（2, 9）→（2）
• 后手：（2）→（） 此时，$X = 5 + 1 + 9 = 15$，$Y = 4 + 7 + 2 = 13$。

由 ChatGPT 4.1 翻译