Hiểu bài toán

Bài toán yêu cầu tìm cách loại bỏ các quân bài ở vị trí giữa để tối đa hóa tổng điểm. Với mỗi quân bài tại vị trí k bị loại bỏ, người chơi nhận được điểm bằng giá trị a[k] * (a[k-1] + a[k+1]) tại thời điểm loại bỏ. Quân bài đầu (0) và cuối (n-1) luôn được giữ lại cho đến cuối cùng. Đây là bài toán quy hoạch động trên cây hoặc dãy con (Chain Matrix Multiplication / Optimal BST variant). Ta cần xác định thứ tự loại bỏ các phần tử để tối đa hóa tổng điểm.

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

Cách Quy hoạch động chuỗi (Chain DP)

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

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

    // dp[l][r]: điểm tối đa khi loại bỏ toàn bộ phần tử từ l+1 đến r-1
    // Khi đó, a[l] và a[r] là các phần tử biên của đoạn con này.
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

    // len là khoảng cách giữa l và r. Ta cần len >= 2 (tức là giữ lại l và r, có phần tử ở giữa)
    // Vòng lặp này tính cho các đoạn con có độ dài từ 2 (khoảng cách 2) trở lên.
    // len = 2 nghĩa là l và r cách nhau 2 đơn vị, có 1 phần tử ở giữa (k).
    for (int len = 2; len < n; ++len) {
        for (int l = 0; l + len < n; ++l) {
            int r = l + len;
            // Thử loại bỏ phần tử k ở giữa l và r làm bước cuối cùng trong đoạn con [l, r]
            // Nếu loại bỏ k, ta nhận điểm a[k] * (a[l] + a[r]).
            // Trước đó, ta phải xử lý đoạn [l, k] và [k, r].
            for (int k = l + 1; k < r; ++k) {
                dp[l][r] = std::max(dp[l][r], dp[l][k] + dp[k][r] + a[k] * (a[l] + a[r]));
            }
        }
    }

    std::cout << dp[0][n - 1] << std::endl;
    return 0;
}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

Đây là phương pháp quy hoạch động kinh điển cho các bài toán loại bỏ phần tử theo thứ tự.

1. Định nghĩa: dp[l][r] là tổng điểm tối đa có thể đạt được khi loại bỏ tất cả các phần tử nằm giữa chỉ số l và r (tức là từ l+1 đến r-1).
2. Công thức truy hồi: Để tính dp[l][r], ta chọn một phần tử k (l < k < r) để loại bỏ cuối cùng trong đoạn [l, r]. Khi k bị loại bỏ, các phần tử còn lại bên trái và bên phải của nó trong đoạn này đã được xử lý xong (tức là các phần tử từ l+1 đến k-1 và k+1 đến r-1 đã bị loại). Điểm nhận được tại bước này là a[k] * (a[l] + a[r]). Do đó: dp[l][r] = max(dp[l][k] + dp[k][r] + a[k] * (a[l] + a[r])) với mọi k trong (l, r).
3. Base case: Nếu r = l + 1 (hoặc r = l + 2 tùy cách tính len), không có phần tử nào ở giữa để loại, giá trị là 0.
4. Kết quả: dp[0][n-1].

Cách Quy hoạch động tối ưu (Optimal)

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

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

    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

    // len là khoảng cách giữa l và r
    for (int len = 2; len < n; ++len) {
        for (int l = 0; l + len < n; ++l) {
            int r = l + len;
            int best = 0;
            // Lặp qua tất cả các k để tìm max
            for (int k = l + 1; k < r; ++k) {
                int current_score = dp[l][k] + dp[k][r] + a[k] * (a[l] + a[r]);
                if (current_score > best) best = current_score;
            }
            dp[l][r] = best;
        }
    }

    std::cout << dp[0][n - 1] << std::endl;
    return 0;
}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

Đây là cách viết tường minh hơn của phương pháp 1. Logic hoàn toàn giống nhau. Độ phức tạp O(n^3) là chấp nhận được với n <= 700 (khoảng 343 triệu phép tính tối đa, có thể chạy trong 1-2s với C++).

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

Bài học kinh nghiệm

• Bài toán có cấu trúc quy hoạch động chuỗi (Chain DP), tương tự bài toán nhân ma trận tối ưu (Matrix Chain Multiplication).
• Giá trị tại một bước (a[k] * (a[l] + a[r])) phụ thuộc vào các phần tử biên của đoạn con hiện tại (lúc loại bỏ k, các phần tử l và r vẫn còn trong dãy).
• Truy hồi qua dp[l][r] bằng cách chia dãy thành 2 dãy con [l, k] và [k, r].

Lỗi thường gặp

• Xác định sai độ dài (len) của đoạn con trong vòng lặp. Nếu len là số lượng phần tử thì công thức khác; ở đây len là khoảng cách chỉ số (r - l) nên vòng lặp bắt đầu từ 2.
• Quên khởi tạo giá trị mặc định cho mảng DP (thường là 0).
• Lỗi truy cập ngoài biên mảng nếu vòng lặp không kiểm soát chặt chẽ l + len < n.