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.


  • 0
    VoCongThanh  commented on April 11, 2026, 8:23 a.m.

    MÌNH CÓ CÁCH DỄ HIỂU HƠN:

    include <bits/stdc++.h>

    define fast cin.tie(0)->syncwithstdio(0)

    define ll long long

    using namespace std; const int N = 3002; const int mod = 1e9 + 7; ll a[N]; ll dp[N][N]; int main(){ fast; ll n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++){ dp[i][i] = a[i]; }

    for(int len = 2; len <= n; len++){
    for(int l = 1; l + len - 1 <= n; l++){
        ll r = l + len - 1;

        dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]); 
        // lấy bên phải và trái
    }
}
cout << dp[1][n];

    }


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

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


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

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