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
Submit ở CSES thì AC còn ở đây thì TLE 🐧, LOL