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.

Độ 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

Please read the guidelines before commenting.


  • -1
    vlthhiep08  commented on Jan. 9, 2025, 9:27 a.m.

    Phải là Taro chứ ạ ?


  • -15
    HoaBanMaTuy  commented on Oct. 6, 2023, 4:10 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.