Hiểu bài toán

Cho một mảng gồm n số nguyên dương a[1], a[2], ..., a[n]. Ban đầu tổng điểm là 0. Thực hiện các thao tác sau cho đến khi mảng có độ dài <= 2:

1. Chọn một chỉ số i (1 < i < n).
2. Cộng min(a[i-1], a[i+1]) vào tổng điểm.
3. Xóa a[i] khỏi mảng (dồn mảng lại).

Mục tiêu: Tìm tổng điểm lớn nhất có thể sau khi thực hiện các thao tác tối ưu.

Các cách tiếp cận

Cách Mô phỏng tối ưu theo greedy (Stack)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<long long> st; // Kho lưu chứa các phần tử chưa bị xóa
    long long total_score = 0;

    for (long long x : a) {
        // Kiểm tra xem có thể xóa phần tử ở giữa stack và x hay không
        // Điều kiện: phần tử ở giữa là 'đáy cốc' (lớn hơn hoặc bằng 2 bên)
        while (st.size() >= 2) {
            long long mid = st.back();
            long long left = st[st.size() - 2];

            if (mid <= left && mid <= x) {
                total_score += min(left, x);
                st.pop_back(); // Xóa mid
            } else {
                break;
            }
        }
        st.push_back(x);
    }

    // Sau khi duyệt hết, xử lý các phần tử còn lại trong stack
    // Chỉ còn lại các phần tử tạo thành dãy đơn điệu giảm dần
    // Cần xóa các phần tử ở giữa để lấy điểm
    // Tối ưu bằng cách xóa các phần tử nhỏ nhất trước
    sort(st.begin(), st.end());
    for (int i = 0; i < (int)st.size() - 2; i++) {
        total_score += st[i];
    }

    cout << total_score << endl;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Giải thuật sử dụng Stack để xử lý các trường hợp có thể xóa ngay lập tức (khi phần tử ở giữa nhỏ hơn 2 bên). Quy trình:

1. Duyệt mảng từ trái sang phải, đẩy phần tử vào Stack.
2. Nếu Stack có >= 2 phần tử và phần tử ở giữa (top-1) nhỏ hơn cả phần tử ở top-2 và phần tử hiện tại (x), ta có thể xóa nó ngay để lấy điểm là min(2 bên). Sau khi xóa, tiếp tục kiểm tra lại điều kiện (do top-2 và x giờ kề nhau).
3. Sau khi duyệt xong, Stack sẽ chứa các phần tử theo thứ tự giảm dần (chỉ có thể xóa thêm các phần tử ở giữa).
4. Để tối ưu điểm, ta sắp xếp Stack và cộng tất cả các giá trị trừ 2 giá trị lớn nhất (vì 2 giá trị lớn nhất sẽ là 2 phần tử cuối cùng còn lại).

Cách Xử lý mảng tại chỗ (In-place)

#include<bits/stdc++.h>
using namespace std;
long long a[1000000],n,s;
int main(){
    freopen("game.inp","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(i>2 && a[i]>=a[i-1] && a[i-1]<=a[i-2])
            s+=min(a[i],a[i-2]),
            a[i-1]=a[i], // Ghi đè giá trị
            i--; // Giảm chỉ số để xử lý tiếp
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n-2;i++) s+=a[i];
    cout<<s;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng mảng đầu vào làm nơi lưu trữ trạng thái thay vì dùng Stack riêng.

1. Khi duyệt mảng, nếu phát hiện a[i-1] là 'đáy cốc' (nhỏ hơn a[i-2] và a[i]), ta cộng điểm, và ghi đè a[i-1] = a[i].
2. Lệnh i-- khiến cho vòng lặp quay lại kiểm tra a[i-1] (vừa được ghi đè) với các phần tử trước đó, tương tự cơ chế Pop trong Stack.
3. Sau cùng, mảng còn lại vẫn cần được xử lý bằng cách sắp xếp và cộng các giá trị nhỏ.

Cách Quy hoạch động (Khó khả thi)

// Pseudocode min locally
LL solve(int l, int r) {
    if (r - l + 1 <= 2) return 0;
    LL res = 0;
    for (int k = l + 1; k < r; k++) {
        res = max(res, min(a[l], a[r]) + solve(l, k) + solve(k, r));
    }
    return res;
}

• Time Complexity: O(N!)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất: thử mọi cách xóa phần tử ở vị trí k. Công thức truy hồi: DP(l, r) = max(DP(l, k) + DP(k, r) + min(a[l], a[r])) với l < k < r. Độ phức tạp là quá lớn (3^n hoặc factorial), không thể chạy được cho n lớn. Đây chỉ là để minh họa tính chất bài toán, không phải lời giải chính xác.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Mọi thao tác xóa phần tử a[i] đều mang lại giá trị là min(a[i-1], a[i+1]).
• Nếu một phần tử a[i] nhỏ hơn hoặc bằng cả 2 hàng xóm (a[i-1] và a[i+1]), nên xóa nó càng sớm càng tốt. Nó không bao giờ là min của 2 phần tử lớn hơn nó.
• Bài toán có thể chia làm 2 giai đoạn: Xóa các 'đáy cốc' cục bộ và xử lý dãy đơn điệu còn lại.
• Trong giai đoạn dãy đơn điệu giảm dần, để tối ưu, ta cần giữ lại 2 phần tử lớn nhất (để tạo thành min cao nhất cho nhau) và xóa phần còn lại (giá trị cộng dồn là tổng các phần tử trừ 2 phần tử lớn nhất).

Lỗi thường gặp

• Lỗi tràn số (Overflow): Tổng điểm có thể lên tới 10^9 * 10^5, phải dùng kiểu long long.
• Sai logic khi xử lý dãy đơn điệu: Nhiều người nhầm tưởng chỉ cần lấy tổng các phần tử trừ 2 phần tử đầu/cuối, nhưng thực tế phải là 2 phần tử lớn nhất.
• Lỗi index: Khi xử lý mảng tại chỗ (Solution 2), việc thay đổi chỉ số i cần cẩn thận để không bị infinite loop hoặc truy cập sai.