CSES - Removal Game | Trò chơi loại bỏ
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có một dãy gồm \(n\) số và hai người chơi luân phiên nhau. Tại mỗi lượt, một người chơi loại bỏ đi số đầu tiên hoặc số cuối cùng ra khỏi danh sách, và điểm của người đó tăng thêm một lượng bằng số đó. Cả hai người chơi đều muốn tối đa hóa điểm của họ.
Số điểm tối đa có thể của người chơi thứ nhất là bao nhiêu nếu cả hai người đều chơi tối ưu?
Input
- Dòng đầu vào đầu tiên chứa một số nguyên \(n\): kích thước của dãy.
- Dòng tiếp theo có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các phần tử của dãy.
Output
- In số điểm tối đa có thể của người chơi thứ nhất.
Constraints
- \(1 \le n \le 5000\)
- \(-10^9 \le x_i \le 10^9\)
Example
Sample input
4
4 5 1 3
Sample output
8
Bình luận
Trong bài đề nói là mỗi người đều chơi tối ưu thì kết quả phải là 7 mới đúng chứ nhỉ?
4 5 1 3
Người thứ 1 lấy số 4 là còn : 5 1 3
Người thứ 2 lấy số 5 là còn : 1 3
Người thứ 1 lấy số 3 là còn : 1
Và người thứ 2 lấy số cuối cùng là 1 thì suy ra:
-Người thứ 1 có 4+3=7 điểm
-Người thứ 2 có 5+1=6 điểm
Mọi người giải thích giúp mình với
-
1
NTT_36
3:07 p.m. 22 Tháng 9, 2024
-
0
thuytien2013
3:18 p.m. 22 Tháng 9, 2024
1 bình luận nữaNgười chơi thứ nhất có thể lấy số 3 vào lần đầu tiên , sau đó người chơi thứ hai chỉ còn cách chọn số 4 hoặc 1 , sau đó người chơi thứ nhất lấy số 5 và được 8 điểm nhé bạn
Cảm ơn bạn nhiều