Atcoder Educational DP Contest L - Deque
Xem dạng PDFTaro 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~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.