Hiểu bài toán

Bài toán yêu cầu tìm chi phí tối thiểu để che phủ n gian hàng được thuê (vị trí cho trước) nằm trong m gian hàng liền nhau. Các tấm bạt có thể mua có kích thước từ 1 đến m, mỗi kích thước w có giá C_w (không đảm bảo tăng dần). Chi phí tối thiểu là tổng giá của các tấm bạt sao cho union của các khoảng che phủ chứa tất cả các gian hàng được thuê. Có thể chồng lấp các tấm bạt.

Về bản chất, ta cần chia dãy vị trí gian hàng thuê thành các nhóm liên tiếp, mỗi nhóm (từ i đến j) sẽ được che bằng một tấm bạt có kích thước tối thiểu là x[j] - x[i] + 1. Chi phí của nhóm này là giá của tấm bạt kích thước đó. Do các tấm bạt có thể chồng lấp, ta luôn có thể chọn mua tấm bạt che chính xác khoảng từ gian hàng đầu tiên đến gian hàng cuối cùng của một nhóm, hoặc lớn hơn, nhưng chi phí tối ưu sẽ là giá thấp nhất của các tấm bạt có kích thước >= khoảng cách cần che. Do đó, ta cần chuẩn hóa chi phí: Cost[w] = min(C_w, Cost[w+1], ..., Cost[m]), tức là giá mua tấm bạt che khoảng cách tối thiểu w là giá thấp nhất cho mọi kích thước >= w.

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

Cách Quy hoạch động cơ bản O(n^2)

#include <bits/stdc++.h>
using namespace std;

vector<int> dp(100001, INT_MAX);
vector<int> c(100001, 0);

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    // Chuẩn hóa chi phí: c[w] là chi phí tối thiểu để che khoảng cách >= w
    int oldmin = 1e7, newmin = 1e7;
    for (int i = m; i >= 1; i--) {
        newmin = min(oldmin, c[i]);
        c[i] = newmin;
        oldmin = newmin;
    }
    dp[1] = c[1];
    dp[0] = 0;
    // dp[i]: chi phí tối thiểu che i gian hàng đầu tiên
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // Gộp các gian hàng từ j+1 đến i vào một nhóm
            // Khoảng cách cần che là a[i] - a[j+1] + 1
            dp[i] = min(dp[i], dp[j] + c[a[i] - a[j + 1] + 1]);
        }
    }
    cout << dp[n];
}

• Time Complexity: O(n^2 + m)
• Space Complexity: O(n + m)

Đây là cách tiếp cận trực tiếp nhất. Ta sắp xếp lại các vị trí gian hàng thuê. Sau đó, ta định nghĩa dp[i] là chi phí tối thiểu để che phủ i gian hàng đầu tiên (từ a[1] đến a[i]). Để tính dp[i], ta xét tất cả các vị trí chia tách j (từ 0 đến i-1). Giả sử ta đã che j gian hàng đầu tiên với chi phí dp[j], thì i-j gian hàng còn lại (từ j+1 đến i) sẽ được che bằng một tấm bạt duy nhất. Kích thước tấm bạt cần thiết là a[i] - a[j+1] + 1. Chi phí cho tấm bạt này là c[a[i] - a[j+1] + 1] (sau khi đã chuẩn hóa). Ta cập nhật dp[i] = min(dp[i], dp[j] + cost).

Trước khi chạy DP, ta cần chuẩn hóa chi phí: duyệt từ m về 1, để c[i] = min(c[i], c[i+1]). Điều này đảm bảo rằng nếu ta cần che một khoảng cách len, ta có thể mua một tấm bạt lớn hơn (kích thước >= len) với giá rẻ hơn.

Độ phức tạp là O(n^2) do hai vòng lặp lồng nhau, và O(m) để chuẩn hóa giá.

Cách Quy hoạch động tối ưu O(n^2)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    for (int i = 0; i < n; i++)
        cin >> x[i];
    sort(x.begin(), x.end());
    vector<long long> c(m + 2), s(m + 2);
    for (int i = 1; i <= m; i++)
        cin >> c[i];
    // Chuẩn hóa chi phí
    s[m] = c[m];
    for (int w = m - 1; w >= 1; w--)
        s[w] = min(s[w + 1], c[w]);
    vector<long long> dem(n + 2, 4e18);
    dem[n + 1] = 0;

    // DP từ phải sang trái
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j++) {
            int L = x[j - 1] - x[i - 1] + 1;
            dem[i] = min(dem[i], dem[j + 1] + s[L]);
        }
    }
    cout << dem[1];
    return 0;
}

• Time Complexity: O(n^2 + m)
• Space Complexity: O(n + m)

Cách tiếp cận này tương đương về độ phức tạp O(n^2) nhưng khác biệt về mặt logic định nghĩa DP.

Ta định nghĩa dem[i] là chi phí tối thiểu để che phủ các gian hàng từ vị trí thứ i đến n (tức là từ x[i-1] đến x[n-1] trong code).

Công trức quy hoạch động: dem[i] = min_{j >= i} ( dem[j+1] + Cost(x[j] - x[i] + 1) )

Ý nghĩa: Để che nhóm gian hàng từ i đến j, ta dùng 1 tấm bạt chi phí s[L] (với L là khoảng cách), và cộng thêm chi phí che phần còn lại từ j+1 trở đi là dem[j+1].

Cài đặt:

• Khởi tạo dem[n+1] = 0.
• Duyệt i từ n giảm dần về 1.
• Duyệt j từ i đến n để thử mọi khả năng gộp nhóm.
• L = x[j-1] - x[i-1] + 1 (Lưu ý kiểm tra chỉ số mảng).

Cách này có thể dễ hiểu hơn theo hướng "chia dãy từ đầu", nhưng về mặt tính toán thì tương đương với cách DP từ trái sang.

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

Bài học kinh nghiệm

• Bài toán có tính chất quy hoạch động kinh điển 'chia dãy'.
• Vấn đề về các tấm bạt có giá không tăng dần có thể được giải quyết bằng cách chuẩn hóa chi phí: Cost[len] = min(Cost[len], Cost[len+1], ..., Cost[m]). Điều này biến bài toán về việc chỉ cần quan tâm đến giá của tấm bạt có kích thước chính xác len sau khi chuẩn hóa.
• Do n khá nhỏ (<= 5000) và m lớn (<= 10^5), thuật toán O(n^2) là tối ưu, trong khi O(m) để xử lý giá là bắt buộc.
• Có hai cách định nghĩa DP: từ trái sang phải (dp[i] che i phần tử đầu) hoặc từ phải sang trái (dem[i] che từ i đến hết). Cả hai đều hoạt động.
• Các vị trí gian hàng phải được sắp xếp lại trước khi xử lý.

Lỗi thường gặp

• Không sắp xếp mảng vị trí: Khiến các gian hàng không liền nhau về mặt logic, phá vỡ thuật toán.
• Lỗi chỉ số mảng (Off-by-one error): Khi tính khoảng cách a[i] - a[j], cần đảm bảo đúng số lượng gian hàng trong khoảng đó.
• Quên chuẩn hóa giá: Nếu chỉ dùng giá gốc C_w, ta có thể bỏ lỡ cơ hội mua tấm bạt lớn hơn nhưng rẻ hơn để che một khoảng nhỏ.
• Sử dụng biến DP thiếu sót: Khởi tạo sai giá trị ban đầu (ví dụ dp[0] phải là 0, các vị trí khác là vô cùng lớn).