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.

Độ phức tạp thời gian: $O (N^{2})$ .

Gọi $d p [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.

$d p [i] [j] = m a x_{j > i} {\begin{cases} a_{i} - d p [i + 1] [j] \\ a_{j} - d p [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à $- d p [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à $d p [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$ .

Copy

#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

Hãy đọc nội quy trước khi bình luận.

-1

vlthhiep08 đã bình luận 9:27:39 sa, 09/01/2025

Phải là Taro chứ ạ ?

-15

HoaBanMaTuy đã bình luận 4:10:32 sa, 06/10/2023

khó hiểu quá

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-16

hoanglong1643 đã bình luận 9:56:55 sa, 22/11/2023

skill issue

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-27

trongtenlinhcbhk64 đã bình luận 2:42:50 ch, 06/10/2023

toi thấy dễ hiểu mà

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.