← 返回题目列表

AtCoder · dp_l

L. 双端队列

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

分数: 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.