Hiểu bài toán

Bài toán mô phỏng một hàng người mua vé. Có N người xếp hàng từ 1 đến N. Mỗi người i có thời gian mua vé riêng là ti. Người bán có thể bán tối đa 2 vé/lần. Do đó, người thứ i+1 có thể rời hàng và nhờ người i mua hộ. Nếu người i mua hộ cả 2 vé (cho i và i+1) thì thời gian là ri (thay vì ti + t{i+1}). Mục tiêu tìm tổng thời gian ít nhất để tất cả mọi người đều mua được vé.

Quyết định: Với mỗi người, chọn một trong hai:

1. Tự mua vé (tốn t_i).
2. Nhờ người sau mua hộ (tốn r_i, và người sau phải mua 2 vé).

Đây là bài toán quy hoạch động kinh điển.

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

Cách Quy hoạch động - Duyệt từ đầu đến cuối

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

int main() {
    int N;
    cin >> N;
    vector<long long> t(N + 1), r(N + 1);
    for (int i = 1; i <= N; i++) cin >> t[i];
    for (int i = 1; i < N; i++) cin >> r[i];

    vector<long long> dp(N + 1, 0);
    dp[1] = t[1];
    if (N >= 2) dp[2] = min(t[1] + t[2], r[1]);

    for (int i = 3; i <= N; i++) {
        // Lựa chọn 1: Người i tự mua vé -> t[i] + dp[i-1]
        // Lựa chọn 2: Người i-1 nhờ người i mua hộ -> r[i-1] + dp[i-2]
        dp[i] = min(dp[i-1] + t[i], dp[i-2] + r[i-1]);
    }

    cout << dp[N] << endl;
    return 0;
}

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

Sử dụng mảng DP:

• dp[i] là chi phí tối thiểu cho i người đầu tiên.
• Công thức truy hồi: dp[i] = min(dp[i-1] + t[i], dp[i-2] + r[i-1]).
• Ý nghĩa: Nếu i tự mua, chi phí là t[i] cộng với chi phí của i-1 người trước. Nếu i-1 nhờ i mua hộ, chi phí là r[i-1] cộng với chi phí của i-2 người trước.
• Đây là cách tiếp cận trực quan nhất.

Cách Quy hoạch động - Duyệt từ cuối đến đầu (Tiết kiệm bộ nhớ)

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

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

    vector<long long> dp(n + 2, 0); // dp[i] là chi phí tối thiểu từ người i đến N

    for (int i = n; i >= 1; i--) {
        dp[i] = a[i] + dp[i + 1]; // Case 1: Tự mua
        if (i < n) {
            dp[i] = min(dp[i], b[i] + dp[i + 2]); // Case 2: Nhờ người sau mua hộ
        }
    }

    cout << dp[1];
    return 0;
}

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

Cách tiếp cận này giải quyết vấn đề từ cuối hàng lên đầu hàng:

• dp[i] là chi phí tối thiểu để phục vụ từ người i đến người N.
• Case 1: Người i tự mua vé (tốn a[i]), rồi lo tiếp cho người i+1.
• Case 2: Người i nhờ người i+1 mua hộ (tốn b[i]), người i+1 đã lo luôn 2 vé, nên nhảy thẳng sang lo cho người i+2.
• Kết quả là dp[1].

Cách Quy hoạch động - Optimization (O(1) space)

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

int main() {
    int N;
    cin >> N;
    vector<long long> t(N + 1), r(N + 1);
    for (int i = 1; i <= N; i++) cin >> t[i];
    for (int i = 1; i < N; i++) cin >> r[i];

    if (N == 1) {
        cout << t[1] << endl;
        return 0;
    }

    long long prev2 = 0;    // dp[i-2]
    long long prev1 = t[1]; // dp[i-1]
    long long curr = 0;

    for (int i = 2; i <= N; i++) {
        curr = min(prev1 + t[i], prev2 + r[i-1]);
        prev2 = prev1;
        prev1 = curr;
    }

    cout << curr << endl;
    return 0;
}

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

Tối ưu bộ nhớ bằng cách chỉ lưu 2 giá trị DP gần nhất thay vì toàn bộ mảng.

• Biến prev2 lưu dp[i-2], prev1 lưu dp[i-1].
• Vòng lặp tính toán curr (dp[i]) và cập nhật lại biến lưu trữ.
• Phù hợp với N lớn nhưng vẫn đảm bảo độ an toàn về bộ nhớ.

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 1 chiều với dependency (phụ thuộc) vào 1 hoặc 2 phần tử trước đó.
• Việc 'mua hộ' tạo thành một cặp (i, i+1) có chi phí r_i, và không ảnh hưởng trực tiếp đến các phần tử trước i-1, chỉ ảnh hưởng đến tổng chi phí tích lũy.
• Bài toán có thể được giải bằng 2 hướng: Tính chi phí tích lũy từ đầu (xây dựng tổng) hoặc tính chi phí còn lại từ cuối (chia để trị/tối ưu từ xa).

Lỗi thường gặp

• Lỗi truy cập mảng: Khi dùng DP từ đầu, cần kiểm tra điều kiện i >= 2 trước khi truy cập dp[i-2] và r[i-1].
• Kiểu dữ liệu: N <= 60000, ti, ri <= 30000. Tổng thời gian có thể lên tới ~1.8 * 10^9, vượt quá giới hạn của int (2 * 10^9). Cần dùng long long (hoặc long trong Pascal).
• Xử lý N=1: Nếu N=1, chỉ có t1, không có r1. Cần xử lý riêng hoặc đảm bảo mảng r có phần tử r[2] (giả sử) hoặc điều chỉnh vòng lặp.