Editorial for Atcoder Educational DP Contest L - Deque
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Độ 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'; }
Comments
Phải là Taro chứ ạ ?
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.