Hiểu bài toán

Bài toán yêu cầu chia một dãy xe gồm N xe thành các đoàn liên tiếp nhau sao cho tổng tải trọng (weight) của mỗi đoàn không vượt quá P. Mỗi đoàn xe sẽ di chuyển một quãng đường L, và tốc độ của cả đoàn được xác định bởi xe có tốc độ thấp nhất trong đoàn (tức là xe có vận tốc v nhỏ nhất, hay thời gian L/v lớn nhất). Mục tiêu là tìm cách chia đoàn để tổng thời gian di chuyển của tất cả các đoàn là nhỏ nhất. Ta cần tính toán thời gian tối thiểu này và in ra với độ chính xác 2 số sau dấu phẩy.

Ví dụ:

• Dữ liệu vào: N, P, L, followed by N cặp (wi, vi).
• Dữ liệu ra: Một số thực là tổng thời gian tối thiểu.

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

Cách Quy hoạch động cơ bản (Duyệt tất cả các đoạn)

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

int main() {
    int n; long long P; double L;
    cin >> n >> P >> L;
    vector<int> w(n+1), v(n+1);
    for(int i=1; i<=n; i++) cin >> w[i] >> v[i];

    double dp[1005];
    dp[0] = 0;

    for(int i=1; i<=n; i++) {
        dp[i] = 1e18; // Khởi tạo giá trị vô cùng lớn
        long long sumW = 0;
        double maxTime = 0;
        // Duyệt ngược từ i về 1 để thử các đoạn [j, i]
        for(int j=i; j>=1; j--) {
            sumW += w[j];
            if(sumW > P) break; // Nếu quá tải thì dừng ngay

            // Tính thời gian của đoạn hiện tại (xe chậm nhất)
            double time = L / (double)v[j];
            if(time > maxTime) maxTime = time;

            dp[i] = min(dp[i], dp[j-1] + maxTime);
        }
    }

    cout << fixed << setprecision(2) << dp[n];
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất. Ta định nghĩa dp[i] là thời gian tối thiểu để xử lý i xe đầu tiên. Để tính dp[i], ta xem xét việc chia đoạn cuối cùng bắt đầu từ vị trí j (với 1 <= j <= i). Đoạn này bao gồm các xe từ j đến i. Ta cần kiểm tra xem tổng tải trọng của đoạn này có vượt quá P không. Nếu không, ta cập nhật dp[i] = min(dp[i], dp[j-1] + time(j...i)). Trong đó time(j...i) là thời gian di chuyển của đoạn, phụ thuộc vào xe chạy chậm nhất trong đoạn đó. Do ta duyệt j giảm dần, ta có thể cập nhật maxTime một cách hiệu quả.

Cách Tối ưu Quy hoạch động (Cắt tỉa)

// Logic tương tự Solution 2
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long P; double L;
    cin >> n >> P >> L;
    vector<int> w(n+1), v(n+1);
    vector<double> t(n+1);
    for(int i=1; i<=n; i++) {
        cin >> w[i] >> v[i];
        t[i] = L / (double)v[i];
    }

    vector<double> dp(n+1, 1e18);
    dp[0] = 0;

    for(int i=1; i<=n; i++) {
        long long sumW = 0;
        double maxT = 0;
        for(int j=i; j>=1; j--) {
            sumW += w[j];
            if(sumW > P) break;
            maxT = max(maxT, t[j]);
            dp[i] = min(dp[i], dp[j-1] + maxT);
        }
    }

    cout << fixed << setprecision(2) << dp[n];
    return 0;
}

• Time Complexity: O(N^2) (trung bình có thể tốt hơn)
• Space Complexity: O(N)

Phương án này về cơ bản là giống phương án 1, nhưng là cách các tác giả đã thực hiện trong bài nộp. Thuật toán vẫn là quy hoạch động O(N^2). Tuy nhiên, việc tối ưu nằm ở chỗ:

1. Tính toán thời gian t[i] trước để không phải chia lặp lại.
2. Sử dụng biến maxT để theo dõi xe chậm nhất trong đoạn đang xét, tránh việc lặp lại tính toán.
3. Điều kiện sumW > P cho phép thoát vòng lặp sớm nếu đoàn xe quá tải, giảm thời gian chạy trong thực tế. Độ phức tạp vẫn là O(N^2) do có 2 vòng lặp lồng nhau, nhưng đây là phương án chấp nhận được với N lên tới 1000.

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

Bài học kinh nghiệm

• Bài toán có tính chất tối ưu con bài toán quy hoạch động (Optimal Substructure): Thời gian tối ưu của N xe phụ thuộc vào thời gian tối ưu của các đoạn xe trước đó.
• Thời gian của một đoàn xe được quyết định bởi xe có vận tốc thấp nhất (thời gian di chuyển lớn nhất) trong đoàn đó.
• Việc duyệt ngược (từ i về 1) cho phép ta dễ dàng duy trì và cập nhật tải trọng tích lũy và thời gian lớn nhất của đoạn hiện tại mà không cần tính toán lại từ đầu.

Lỗi thường gặp

• Sai số số thực (Floating point error): Khi so sánh tổng tải trọng với P, cần đảm bảo biến sumW có kiểu dữ liệu đủ lớn (ví dụ long long) để tránh tràn số nếu N * w_i vượt quá giới hạn của int.
• Chọn sai độ dài mảng: Nếu khai báo mảng tĩnh, cần đảm bảo kích thước đủ cho N (ví dụ N <= 1000 trong bài này).
• Định dạng xuất: Bài yêu cầu in ra số thực với 2 số thập phân, cần sử dụng fixed và setprecision(2).