Atcoder Educational DP Contest L - Deque

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Taro và Jiro chơi với nhau một trò chơi như sau:

Cho tập hợp gồm ~N~ số nguyên dương ~a=(a_1,a_2,...,a_N)~. Hai người chơi sẽ lần lượt thực hiện các nước đi sau đến khi ~a~ rỗng, với Taro là người bắt đầu:

  • Loại bỏ phần tử đầu tiên hoặc cuối cùng của dãy ~a~. Người chơi đó sẽ kiếm được ~x~ điểm, với ~x~ là phần tử bị loại bỏ.

Cho ~X~ và ~Y~ lần lượt là số điểm của Taro và Jiro sau khi trò chơi kết thúc. Taro muốn ~X - Y~ lớn nhất có thể, trong Jiro lại muốn làm ~X - Y~ bé nhất có thể.

Giả sử cả hai người đều chơi tối ưu, tìm giá trị của ~X - Y~.

Input:

  • Dòng thứ nhất chứa hai số nguyên dương ~N (1 \leq N \leq 3000)~.
  • Dòng thứ hai chứa ~N~ số nguyên dương thỏa mãn ~a_1, a_2, a_3, ..., a_N (1 \leq a_i \leq 10^9)~.

Output:

  • In ra giá trị ~X - Y~ cần tìm.

Sample 1

Input
4
10 80 90 30
Output
10
Giải thích

Trò chơi diễn ra như sau nếu hai người đều chơi tối ưu (với phần tử được in đậm là phần tử được chọn):

  • Taro: (10, 80, 90, 30) → (10, 80, 90)
  • Jiro: (10, 80, 90) → (10, 80)
  • Taro: (10, 80) → (10)
  • Jiro: (10) → ()

Ở đây, ~X = 30 + 80 = 110~ và ~Y = 90 + 10 = 100~.

Sample 2

Input
3
10 100 10
Output
-80
Giải thích:

Trò chơi diễn ra như sau nếu hai người đều chơi tối ưu (với phần tử được in đậm là phần tử được chọn):

  • Taro: (10, 100, 10) → (100, 10)
  • Jiro: (100, 10) → (10)
  • Taro: (10) → ()

Ở đây, ~X=10+10=20~ và ~Y=100~.

Sample 3

Input
1
10
Output
10

Sample 4

Input
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
Output
4999999995

Sample 5

Input
6
4 2 9 7 1 5
Output
2
Giải thích:

Trò chơi diễn ra như sau nếu hai người đều chơi tối ưu (với phần tử được in đậm là phần tử được chọn):

  • Taro: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)
  • Jiro: (4, 2, 9, 7, 1) → (2, 9, 7, 1)
  • Taro: (2, 9, 7, 1) → (2, 9, 7)
  • Jiro: (2, 9, 7) → (2, 9)
  • Taro: (2, 9) → (2)
  • Jiro: (2) → ()

Ở đây, ~X=5+1+9=15~ và ~Y=4+7+2=13~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.