Phép toán với ngăn xếp hai đầu
Xem PDF
Điểm:
550
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
\(Kaninho\) và \(Henry\) chơi với nhau một trò chơi như sau:
Ban đầu, họ được cho một dãy số \(a=(a_1,a_2,\cdots,a_n)\). Họ lần lượt thực hiện phép toán dưới đây cho đến khi dãy \(a\) rỗng, bắt đầu từ \(Kaninho\):
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ỏ.
Gọi \(X\) và \(Y\) lần lượt là số điểm của \(Kaninho\) và \(Henry\) sau khi trò chơi kết thúc. \(Kaninho\) cố gắng làm \(X−Y\) lớn nhất có thể, trong khi \(Henry\) muốn \(X−Y\) nhỏ 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 số nguyên \(N(1 \leq N \leq 3000)\)
- Dòng thứ hai, chứa \(n\) số nguyên \(a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)\)
Output
- In ra giá trị cần tìm
Example
Test 1
Input
4
10 80 90 30 Output
10Note
Quá trình chơi tối ưu của hai người chơi như sau:
- \(Kaninho\):\((10,80,90,30)\)→\((10,80,90)\)
- \(Henry\):\((10,80,90)\)→\((10,80)\)
- \(Kaninho\):\((10,80)\)→\((10)\)
- \(Henry\):\((10)\)→\(()\)
Ở đây \(X=30+80=110\) và \(Y=90+10=100\)
Bình luận
Suggest bài toán khó hơn với K hàng đợi 10^6 phần tử
Vẫn là đệ quy có nhớ :v