D - Card Taking Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君と青木君が、カードを使ったゲームで遊びます。

テーブルの上に N 枚のカードが一列に並べられており、左から i 番目のカードには整数 V_i が書かれています。なお、V_i は負の値である場合もあります。

二人は以下のルールに従ってカードを取り合います。

  • 高橋君が先手、青木君が後手で、交互に行動します。
  • 自分のターンでは、テーブルに残っているカードの列の 左端 または 右端 のカードをちょうど1枚選んで取り、自分の手元に置きます。取られたカードはテーブルから除かれ、残りのカードの並び順は変わりません。
  • すべてのカードが取られたらゲームは終了します。

二人はお互いの戦略を含むすべての情報を知っており、それぞれ自分が取ったカードに書かれた整数の合計を最大化するように最適に行動します。

二人が最適に行動したとき、高橋君が取ったカードに書かれた整数の合計から青木君が取ったカードに書かれた整数の合計を引いた値を求めてください。

制約

  • 1 \leq N \leq 3000
  • -10^9 \leq V_i \leq 10^9
  • 入力はすべて整数である。

入力

N
V_1 V_2 \ldots V_N
  • 1 行目には、カードの枚数を表す整数 N が与えられる。
  • 2 行目には、各カードに書かれた整数 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。ここで V_i は左から i 番目のカードに書かれた整数である。

出力

二人が最適に行動したとき、高橋君が取ったカードに書かれた整数の合計から青木君が取ったカードに書かれた整数の合計を引いた値を 1 行で出力せよ。

入力例 1

4
3 1 2 5

出力例 1

3

入力例 2

4
-1 5 -3 2

出力例 2

11

入力例 3

10
8 -3 5 12 -7 2 9 -1 6 4

出力例 3

15

入力例 4

20
15 -8 23 4 -12 7 19 -3 11 6 -5 14 2 -9 18 1 -6 10 8 -2

出力例 4

53

入力例 5

1
-1000000000

出力例 5

-1000000000

Score : 400 pts

Problem Statement

Takahashi and Aoki play a game using cards.

N cards are arranged in a row on the table, and the i-th card from the left has an integer V_i written on it. Note that V_i may be negative.

The two players take cards according to the following rules:

  • Takahashi goes first, Aoki goes second, and they take turns alternately.
  • On their turn, a player chooses exactly one card from either the left end or the right end of the row of cards remaining on the table, takes it, and places it in their hand. The taken card is removed from the table, and the order of the remaining cards does not change.
  • The game ends when all cards have been taken.

Both players know all information including each other's strategies, and each plays optimally to maximize the sum of the integers written on the cards they have taken.

When both players play optimally, find the value obtained by subtracting the sum of the integers written on the cards Aoki took from the sum of the integers written on the cards Takahashi took.

Constraints

  • 1 \leq N \leq 3000
  • -10^9 \leq V_i \leq 10^9
  • All inputs are integers.

Input

N
V_1 V_2 \ldots V_N
  • The first line contains an integer N representing the number of cards.
  • The second line contains the integers V_1, V_2, \ldots, V_N written on each card, separated by spaces. Here, V_i is the integer written on the i-th card from the left.

Output

Print in one line the value obtained by subtracting the sum of the integers written on the cards Aoki took from the sum of the integers written on the cards Takahashi took, when both players play optimally.

Sample Input 1

4
3 1 2 5

Sample Output 1

3

Sample Input 2

4
-1 5 -3 2

Sample Output 2

11

Sample Input 3

10
8 -3 5 12 -7 2 9 -1 6 4

Sample Output 3

15

Sample Input 4

20
15 -8 23 4 -12 7 19 -3 11 6 -5 14 2 -9 18 1 -6 10 8 -2

Sample Output 4

53

Sample Input 5

1
-1000000000

Sample Output 5

-1000000000