分数: 100 点
问题陈述
太郎和次郎将进行以下游戏。
最初,他们被给予一个序列 a = (a_1, a_2, \ldots, a_N)。 直到 a 变空,两名玩家交替执行以下操作,从太郎开始:
- 删除开头或结尾的元素 a。玩家赚取 x 点,其中 x 是删除的元素。
让 X 和 Y 分别是Taro和Jiro在比赛结束时的总得分。 太郎试图最大化 X - Y,而 Jiro 则试图最小化 X - Y.
假设两个玩家发挥最佳,找到结果值 X - Y.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 3000
- 1 \leq a_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N
输出
打印结果值 X - Y,假设两名玩家发挥最佳。
示例输入 1
4 10 80 90 30
示例输出 1
10
当两个玩家发挥最佳状态时,游戏进行如下(被删除的元素以粗体表示):
- 太郎: (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
3 10 100 10
示例输出 2
-80
例如,当两个玩家发挥最佳时,游戏进行如下:
- 太郎:(10, 100, 10) → (100, 10)
- 二郎:(100, 10) → (10)
- 太郎:(10) → ()
在这里, X = 10 + 10 = 20 和 Y = 100.
示例输入 3
1 10
示例输出 3
10
示例输入 4
10 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
示例输出 4
4999999995
答案可能不适合 32 位整数类型。
示例输入 5
6 4 2 9 7 1 5
示例输出 5
2
例如,当两个玩家发挥最佳时,游戏进行如下:
- 太郎: (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.