<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.9}}}}}\)
</button>

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
\(\color{orange}{\text{Mục lục}}\)
</button>

\(\color{#300000}{\text{1. Hint <Cày trâu>}}\)

• \(\color{#903030}{\text{<Cày trâu>}}\) Thử chọn từng bên, và gọi kết quả là \(A, B\). Nếu lượt hiện tại là Kaninho thì lấy \(max(A, B)\), ngược lại lấy \(min(A, B)\)

Gọi kết quả tối ưu đoạn \([L, R]\) là \(magic(L, R)\), thì ta xét việc chọn \(a[L] + magic(L + 1, R)\) hoặc \(a[R] + magic(L, R - 1)\)

\(\color{#c01515}{\text{1. Approach <Cày trâu>}}\)

• \(\color{#f03030}{\text{<Mục tiêu>}}\) Giả sử ta cố gắng tối đa hóa giá trị \(X\) (vì \(X\) càng lớn thì \(X - Y\) càng lớn)

Vậy kết quả của nó sẽ là \(magic(L, R) = max(a[L] + \dots, a[R] + \dots)\)

Giả sử mình chọn \(a[L]\), xét \(magic(L + 1, R)\), người còn lại sẽ cố chọn sao cho giá trị thêm vào của đối thủ nhỏ nhất \(= min(magic(L + 2, R - 0), magic(L + 1, R - 1))\).

Giả sử mình chọn \(a[R]\), xét \(magic(L, R - 1)\), người còn lại sẽ cố chọn sao cho giá trị thêm vào của đối thủ nhỏ nhất \(= min(magic(L + 1, R - 1), magic(L + 0, R - 2))\)

\(max(X)\) khi chọn \(a[L]\) là \(A = a[L] + min(magic(L + 2, R - 0), magic(L + 1, R - 1))\)

\(max(X)\) khi chọn \(a[R]\) là \(B = a[R] + min(magic(L + 1, R - 1), magic(L + 0, R - 2))\)

\(max(X)\) khi được chọn \(a[L]\) hoặc \(a[R]\) là \(max(A, B)\)

• \(\color{#f03030}{\text{<Phân tích độ phức tạp>}}\) \(O(2^n)\)

Số hướng chọn tại mỗi bước: 2 cách là chọn \(a[L]\) hoặc \(a[R]\)

Số lần chọn tất cả: \(R - L = n\)

\(\color{#88B4B4}{\text{1. Code tham khảo<TLE> }}\): Cày trâu

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(2^n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

int n;
vector<int> a;
ll magic(ll L = 0, ll R = n - 1) {
    if (L >= R + 1) return 0;
    if (L >= R - 1) return max(a[L], a[R]);

    ll A = a[L] + min(magic(L + 2, R - 0), magic(L + 1, R - 1));
    ll B = a[R] + min(magic(L + 1, R - 1), magic(L + 0, R - 2));
    return max(A, B);
}

int main()
{
    cin >> n;
    a.resize(n);

    ll sum = 0;
    for (int &t : a)
    {
        cin >> t;
        sum += t;
    }

    ll x = magic();
    ll y = sum - x;
    cout << x - y;
    return 0;
}

\(\color{#300000}{\text{2. Hint <Quy hoạch động>}}\)

• \(\color{#903030}{\text{<Đệ quy có nhớ>}}\) Giờ mình chỉ cần thêm nhớ cho code trên là xong 🙂

Mình cần lưu 2 trạng thái \([L][R]\) để có được \(f[L][R]\) là giá trị tối ưu đoạn \([L \dots R]\) hay \(f[L][R] = magic(L, R))\)

\(\color{#c01515}{\text{2. Approach <Đệ quy có nhớ> <Quy hoạch động>}}\)

• \(\color{#f03030}{\text{<Phân tích độ phức tạp>}}\) \(O(n^2)\)

Số trạng thái: \(O(n^2)\) là số cách chọn \([L][R]\) cần xét

Chi phí chuyển: \(O(1)\) là phép gán giá trị và lấy \(min(), max()\)

\(\color{#009933}{\text{2. Code tham khảo<Accepted> }}\): Đệ quy có nhớ

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n^2)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

int n;
vector<int> a;
vector<vector<ll> > f;
ll magic(ll L = 0, ll R = n - 1) {
    if (f[L][R] != -LINF) return f[L][R];
    if (L >= R + 1) return f[L][R] = 0;
    if (L >= R - 1) return f[L][R] = max(a[L], a[R]);

    ll A = a[L] + min(magic(L + 2, R - 0), magic(L + 1, R - 1));
    ll B = a[R] + min(magic(L + 1, R - 1), magic(L + 0, R - 2));
    return f[L][R] = max(A, B);
}

int main()
{
    cin >> n;
    a.resize(n);
    f.assign(n, vector<ll>(n, -LINF));

    ll sum = 0;
    for (int &t : a)
    {
        cin >> t;
        sum += t;
    }

    ll x = magic();
    ll y = sum - x;
    cout << x - y;
    return 0;
}

\(\color{#009933}{\text{2. Code tham khảo<Accepted> }}\): Quy hoạch động, giải trực tiếp

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n^2)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<vector<ll> > dp(n, vector<ll>(n));
    for (int r = 0; r < n; ++r)
    {
        cin >> a[r];
        dp[r][r] = a[r];
        for (int l = r - 1; l >= 0; --l)
            dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
    }

    cout << dp[0][n - 1];
}

\(\color{#300000}{\text{3. Hint <Tham lam>}}\)

• \(\color{#903030}{\text{Nhận xét 0: }}\) Không phải mọi nhận xét dưới đây đều giúp nhìn ra thuật toán hoan chỉnh (")> Đôi khi nó vô nghĩa, nhưng việc xét các trường hợp như vậy mới là bản chất của tham lam có tính toán 😃

Bạn đọc chỉ cần quan tâm những nhận xét tiếp cận lời giải

• \(\color{#903030}{\text{Nhận xét 1: }}\) Việc tối đa hóa \(max(X - Y)\) là việc chọn \(max(X)\). Việc tối thiểu hóa \(min(X - y)\) là việc chọn \(max(Y)\)

Vì vậy ta sẽ xem trò chơi này như 2 thằng \(X\) và \(Y\) đang muốn tối đa hóa giá trị của nó

• \(\color{#903030}{\text{Nhận xét 2: }}\) Nếu trong mảng có một thằng có giá trị bằng tổng cả mảng trừ nó gộp lại thì việc chọn nó sẽ chắc chắn dành chiến thắng

Trong trường hợp này ta sẽ cố gắng ăn được nó, hoặc dù chơi kiểu gì cũng bị ép thua thì ta sẽ cố ăn các thằng rìa xung quanh sao cho tổng \(X\) lớn nhất

• \(\color{#903030}{\text{Nhận xét 3: }}\) Trong tất cả các lựa chọn, việc có thể lấy thằng giá trị to nhất khi có thể hoặc khi so với giá trị khác luôn mang lại kết quả tối ưu

Bạn đọc tự chứng minh xem như bài tập (sẽ phải xét nhiều trường hợp)

• \(\color{#903030}{\text{Nhận xét 4: }}\) Nếu không lấy được thằng to nhất thì ta chỉ có thể lấy 2 thằng kế bên

Vì có những trường hợp mà mình không thể ăn được thằng lớn nhất, giả xử \(A < B > C\), thì mình phải ăn \(A\) hoặc \(C\) thì nó mới ăn được \(B\)

• \(\color{#903030}{\text{Nhận xét 5: }}\) Nếu có nhiều thằng max thì mình chỉ quan tâm 2 con gần \(L\) và \(R\) nhất

Vì những thằng ở max giữa chỉ được xét sau 2 thằng max ngoài cùng

• \(\color{#903030}{\text{Nhận xét 6: }}\) Kể cả không lấy được thằng \(max\) bạn vẫn có thể hơn điểm. Vì thế không phải lúc nào chọn thằng max cũng là cách tối ưu

Lưu ý rằng hàm tham lam ta mục tiêu không phải nhắm liên tục vào để ăn thằng max cho mình

• \(\color{#903030}{\text{Nhận xét 7: }}\) Việc nén các bộ 3 số kề nhau \((A, B, C)\) thỏa \(B\) là số lớn nhất trong phần mảng hiện tại. Lúc này ta biến \(A \leq B \geq C\) thành \((A + C - B)\) không làm ảnh hưởng kết quả bài toán

Bạn đọc tự chứng minh dựa vào các nhận xét trước - P/S: mình không đủ trinh chứng minh 😢

• \(\color{#903030}{\text{Nhận xét 8: }}\) Ta cần phải biết vị trí số \(max\) tiếp theo càng nhanh càng tốt

Vì độ phức tạp tổng thể phụ thuộc vào việc tìm thằng \(max\) cả mảng tiếp theo

• \(\color{#903030}{\text{Nhận xét 9: }}\) Ta cần phải xóa phần tử \(max\) và dồn mảng lại càng nhanh càng tốt

Vì độ phức tạp tổng thể phụ thuộc vào việc xóa đi phần tử để tìm max lần tiếp theo

• \(\color{#903030}{\text{Nhận xét 10: }}\) Nếu ta liên tục nén các phần tử, ta sẽ thu được một dãy giảm dần về giữa hay \(a_1 \geq a_2 \geq \dots \geq a_k \leq \dots \leq a_{n - 1} \leq a_n\)

Khi này ta có thể tính \(max\) trong \(O(1)\)

• Sau khi nén mảng, ta sẽ sử dụng tiếp thuật toán tham lam trên mảng bitonic(\(a_1 \geq a_2 \geq \dots \geq a_k \leq \dots \leq a_{n - 1} \leq a_n\))

Gọi \(L, R\) là 2 con trỏ ta xét. Lấy \(V = max(a[L], a[R])\) và dịch chuyển con trỏ sau khi lấy

Nếu tới lượt mình thì cộng vào \(X\) giá trị \(V\), không thì cộng vào \(Y\) giá trị \(V\)

Hoặc đặt \(D = X - Y\) thì mình sẽ cộng \(V\) khi đến lượt mình và trừ \(V\) khi dến lượt đấu thủ

\(\color{#c01515}{\text{3. Approach <Tham lam>}}\)

• \(\color{#f03030}{\text{Phân tích độ phức tạp}}\) \(O(n) \times O(f(x) + g(x))\) với \(O(n)\) là việc duyệt từng đỉnh \(O(f(x))\) là việc tìm \(max\) và \(O(g(x))\) là việc xóa phần tử

Nếu dùng trâu đề thì \(O(n) \times O(n + n)\)

Nhận xét 5 để tìm \(max\) trên đoạn. Nếu dùng cây BIT đặc biệt, Segment Tree thì \(O(n) \times O(log(n) + n)\)

Nhận xét 5 và 6, để tìm và xóa phần tử trên đoạn. Nếu dùng CTDL Treap thì \(O(n) \times O(log(n) + log(n))\)

Nếu cài bằng Stack, Deque thì \(O(n) \times O(n + n)\). Tuy nhiên từ nhận xét \(7\), nếu ta giải trực tiếp, độ phức tạp chỉ còn \(O(n) \times O(1 + 1)\)

• Mặc dù nói là cài bằng \(Deque\) nhưng việc tìm 3 thằng ở đầu, ở áp đầu, ở áp áp đầu nói chung là 3 thằng cuối của \(Deque\) sẽ khá khó khăn.

Nên ta sẽ sài \(vector\) để biểu diễn giá trị và nhận các giá trị \(v_i \forall \{i \in \mathbb{N}, i \in [0, n)\ \}\)

Khi \(i < 2\) thì ta không thể nén vì mảng chỉ có 2 phần tử \(v[] = \{v_0, v_1\}\)

Ngược lại ta nén \(v[i - 2] = v[i - 2] - v[i - 1] + v[i]\). Rồi lùi con trỏ đi 2 đơn vị \(i = i - 2\) và giảm độ dài mảng 2 đơn vị \(n = n - 2\)

• Sau khi nén mảng, ta sẽ sử dụng tiếp thuật toán tham lam

\(\color{#009933}{\text{3. Code tham khảo<Accepted> }}\): CTDL, Deque, Giải trực tiếp, Tham lam, Concept, Two-pointers

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    vector<ll> v(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
        for (; i >= 2 && v[i - 2] <= v[i - 1] && v[i - 1] >= v[i]; i -= 2, n -= 2)
            v[i - 2] += v[i] - v[i - 1];
    }

    ll res = 0;
    for (int l = 0, r = n - 1, t = 1; l <= r; t = -t)
    {
        res += t *((v[l] > v[r]) ? v[l++] : v[r--]);
    }
    cout << res;

    return 0;
}