Hướng dẫn giải của Atcoder Educational DP Contest L - Deque
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Độ phức tạp thời gian: ~O(N^2)~.
Gọi ~dp[i][j]~ là điểm tối ưu cho Jiro ~(X-Y)~ trong đoạn ~[i,j]~. Từ đó, ta có thể thêm ~a_i~ vào bên trái của đoạn, hoặc ~a_j~ vào bên phải của đoạn. Khi ta có cách chuyển đổi trạng thái như sau.
$$dp[i][j] = max_{j>i}\begin{cases} a_i−dp[i+1][j] \\ a_j−dp[i][j−1]\\ \end{cases}$$
Lí do ta có cách chuyển đổi trạng thái như vậy là vì khi giải bài toán trên một đoạn ~[i,j]~ bất kì nếu như chọn phần tử ~a[i]~ thì ta giải bài toán trên đoạn ~[i+1,j]~ cho đối thủ mà kết quả tối ưu cho bài toán này là ~-dp[i+1][j]~ do vai trò lúc này hai người chơi hoán đổi cho nhau. Tương tự với khi chọn phần tử ~a[j]~.
Trạng thái ban đầu là ~dp[i][i] = a_i~ vì chỉ có duy nhất một thao tác được thực hiện cho đoạn độ dài ~1~.
#include <bits/stdc++.h> using namespace std; long long dp[3001][3001]; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> a(n); for (int& x : a) cin >> x; for (int i = 0; i < n; ++i) dp[i][i] = a[i]; for (int i = n - 1; i >= 0; i--) for (int j = i + 1; j < n; ++j) dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]); cout << dp[0][n - 1] << '\n'; }
Bình luận
Phải là Taro chứ ạ ?
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.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.