Trong một cuộc đua Công thức 1 (F1), việc lựa chọn lốp xe đóng vai trò cực kỳ quan trọng, đặc biệt khi điều kiện thời tiết thay đổi bất thường giữa các vòng đua. Để giành chiến thắng, các đội đua cần lập kế hoạch chiến lược để tối thiểu hóa thời gian hoàn thành toàn bộ cuộc đua, có tính đến thời gian dừng tại pit để thay lốp và hiệu suất của từng loại lốp trong từng điều kiện thời tiết cụ thể của mỗi vòng.

F1 được trang bị công nghệ khí tượng tiên tiến, cho phép đo lường chính xác điều kiện thời tiết cho từng vòng đua. Ban tổ chức cung cấp nhiều loại lốp khác nhau, và các xe đua có thể sử dụng bất kỳ loại nào khi xuất phát. Sau mỗi vòng, tay đua có thể chọn tiếp tục với lốp hiện tại hoặc vào pit để thay sang một loại lốp khác. Việc thay lốp sẽ tốn một khoảng thời gian cố định.

Bài toán đặt ra là: Với số vòng đua, số loại lốp, thời gian thay lốp, và thời gian hoàn thành một vòng của mỗi loại lốp trong mỗi vòng đua đã được xác định, hãy tính tổng thời gian ngắn nhất để hoàn thành toàn bộ cuộc đua.

Định dạng đầu vào

Dòng đầu tiên chứa ba số nguyên n, m, c (1 ≤ n, m ≤ 1,000, 1 ≤ c ≤ 1,000,000), lần lượt biểu thị tổng số vòng đua, số loại lốp và thời gian dừng tại pit để thay lốp.

n dòng tiếp theo, mỗi dòng gồm m số nguyên. Số thứ j trên dòng thứ i (ký hiệu t[i][j]) (1 ≤ t[i][j] ≤ 1,000,000) biểu thị thời gian cần thiết để hoàn thành vòng đua i khi sử dụng loại lốp j.

Định dạng đầu ra

Một số nguyên s, là tổng thời gian ngắn nhất để hoàn thành cuộc đua.

Ví dụ

Ví dụ đầu vào

4 3 30
50 60 100
70 50 100
10 50 90
100 30 10

Ví dụ đầu ra

170

Ràng buộc

Thời gian chạy cho mỗi test case là 1 giây.

Đối với 30% dữ liệu: n ≤ 15, m ≤ 2.

Giải pháp bằng Quy hoạch động

Chúng ta có thể giải quyết bài toán này bằng kỹ thuật quy hoạch động (Dynamic Programming - DP).

Định nghĩa trạng thái dp[i][j] là thời gian ngắn nhất để hoàn thành vòng đua i và kết thúc vòng đua đó bằng loại lốp j.

Khởi tạo

Đối với vòng đua đầu tiên (i = 1), thời gian để hoàn thành chỉ đơn giản là thời gian sử dụng từng loại lốp trong vòng đó:

dp[1][j] = t[1][j] cho mọi loại lốp j từ 1 đến m.

Chuyển trạng thái

Để tính dp[i][j] (thời gian ngắn nhất hoàn thành vòng i với lốp j), chúng ta có hai lựa chọn ở vòng i-1:

1. Tiếp tục sử dụng loại lốp j: Nếu ở vòng i-1 chúng ta cũng đã sử dụng loại lốp j, thì tổng thời gian đến hết vòng i sẽ là dp[i-1][j] + t[i][j].
2. Thay lốp tại trạm dừng: Nếu chúng ta quyết định thay lốp từ một loại lốp k bất kỳ sang loại lốp j trước khi bắt đầu vòng i. Thời gian này sẽ là thời gian ngắn nhất để hoàn thành vòng i-1 bằng bất kỳ loại lốp nào (gọi là min_prev_lap), cộng thêm thời gian thay lốp c, sau đó cộng thêm thời gian chạy vòng i với lốp j (t[i][j]).
   min_prev_lap = min(dp[i-1][k]) cho mọi k từ 1 đến m.

Từ đó, công thức chuyển trạng thái là:

dp[i][j] = min(dp[i-1][j], min_prev_lap + c) + t[i][j]

Kết quả cuối cùng

Thời gian ngắn nhất để hoàn thành toàn bộ cuộc đua sẽ là giá trị nhỏ nhất trong số dp[n][j] cho tất cả các loại lốp j từ 1 đến m.

Mã nguồn (Quy hoạch động 2D)

Đoạn mã sau đây minh họa cách triển khai giải pháp quy hoạch động sử dụng mảng 2 chiều:

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::min

const int INF = 1e9 + 7; // Sử dụng một giá trị lớn đại diện cho vô cùng

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int numLaps, numTireTypes, changeTimeCost;
    std::cin >> numLaps >> numTireTypes >> changeTimeCost;

    // lapTimes[i][j] là thời gian hoàn thành vòng i với loại lốp j
    // Sử dụng 1-based indexing cho dễ đồng bộ với đề bài
    std::vector<std::vector<int>> lapTimes(numLaps + 1, std::vector<int>(numTireTypes + 1));
    for (int i = 1; i <= numLaps; ++i) {
        for (int j = 1; j <= numTireTypes; ++j) {
            std::cin >> lapTimes[i][j];
        }
    }

    // dp[i][j] là thời gian ngắn nhất để hoàn thành vòng i, kết thúc với loại lốp j
    std::vector<std::vector<int>> dp(numLaps + 1, std::vector<int>(numTireTypes + 1));

    // Khởi tạo vòng đầu tiên (Lap 1)
    for (int j = 1; j <= numTireTypes; ++j) {
        dp[1][j] = lapTimes[1][j];
    }

    // Tính toán cho các vòng từ 2 đến numLaps
    for (int i = 2; i <= numLaps; ++i) {
        int minTimePrevLap = INF;
        // Tìm thời gian ngắn nhất để hoàn thành vòng i-1 với bất kỳ loại lốp nào
        for (int j = 1; j <= numTireTypes; ++j) {
            minTimePrevLap = std::min(minTimePrevLap, dp[i-1][j]);
        }

        for (int j = 1; j <= numTireTypes; ++j) {
            // Lựa chọn 1: Giữ nguyên lốp j từ vòng i-1
            int optionKeepTire = dp[i-1][j];
            // Lựa chọn 2: Thay lốp tại trạm dừng
            int optionChangeTire = minTimePrevLap + changeTimeCost;

            // Chọn lựa chọn tốt hơn, sau đó cộng thêm thời gian chạy vòng hiện tại với lốp j
            dp[i][j] = std::min(optionKeepTire, optionChangeTire) + lapTimes[i][j];
        }
    }

    // Tìm thời gian ngắn nhất để hoàn thành toàn bộ cuộc đua (từ vòng cuối cùng)
    int minTotalTime = INF;
    for (int j = 1; j <= numTireTypes; ++j) {
        minTotalTime = std::min(minTotalTime, dp[numLaps][j]);
    }

    std::cout << minTotalTime << std::endl;

    return 0;
}

Tối ưu hóa không gian (Quy hoạch động 1D)

Nhận thấy rằng dp[i][j] chỉ phụ thuộc vào các giá trị từ dp[i-1]. Điều này cho phép chúng ta tối ưu hóa không gian lưu trữ từ O(N*M) xuống O(M). Chúng ta có thể sử dụng một mảng dp một chiều để lưu trữ thời gian ngắn nhất cho vòng đua *hiện tại*.

Khi tính toán cho vòng đua i, mảng dp sẽ chứa các giá trị của vòng i-1. Để thực hiện điều này, trước khi cập nhật các giá trị dp[j] cho vòng i, chúng ta cần tính minOverallTimeFromPreviousLap dựa trên các giá trị dp[j] *cũ* (tức là của vòng i-1). Sau đó, chúng ta có thể cập nhật dp[j] bằng cách sử dụng một mảng tạm thời hoặc xử lý cẩn thận để tránh ghi đè dữ liệu cần thiết.

Mã nguồn (Quy hoạch động 1D đã tối ưu)

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::min

const int MAX_VAL = 1e9 + 7; // Sử dụng một giá trị lớn đại diện cho vô cùng

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int totalLaps, tireCount, pitStopCost;
    std::cin >> totalLaps >> tireCount >> pitStopCost;

    std::vector<std::vector<int>> lapDurations(totalLaps + 1, std::vector<int>(tireCount + 1));
    for (int i = 1; i <= totalLaps; ++i) {
        for (int j = 1; j <= tireCount; ++j) {
            std::cin >> lapDurations[i][j];
        }
    }

    // minTimesCurrentLap[j] sẽ lưu thời gian ngắn nhất để hoàn thành vòng hiện tại, kết thúc với loại lốp j
    // Ban đầu, nó sẽ lưu giá trị cho vòng 1
    std::vector<int> minTimesCurrentLap(tireCount + 1);

    // Khởi tạo cho vòng đua đầu tiên (Lap 1)
    for (int j = 1; j <= tireCount; ++j) {
        minTimesCurrentLap[j] = lapDurations[1][j];
    }

    // Tính toán cho các vòng từ 2 đến totalLaps
    for (int i = 2; i <= totalLaps; ++i) {
        int minOverallTimeFromPreviousLap = MAX_VAL;
        // Tìm thời gian tối thiểu để hoàn thành vòng (i-1) với bất kỳ loại lốp nào.
        // Các giá trị trong minTimesCurrentLap hiện tại là của vòng i-1.
        for (int j = 1; j <= tireCount; ++j) {
            minOverallTimeFromPreviousLap = std::min(minOverallTimeFromPreviousLap, minTimesCurrentLap[j]);
        }

        // Tạo một bản sao tạm thời của các giá trị minTimesCurrentLap từ vòng trước
        // để sử dụng khi tính toán cho vòng hiện tại mà không bị ghi đè dữ liệu.
        std::vector<int> tempPrevLapMinTimes = minTimesCurrentLap;

        for (int j = 1; j <= tireCount; ++j) {
            // Lựa chọn 1: Giữ nguyên lốp j từ vòng i-1
            int optionKeepSameTire = tempPrevLapMinTimes[j];
            // Lựa chọn 2: Thay lốp từ bất kỳ loại nào sang lốp j
            int optionChangeTire = minOverallTimeFromPreviousLap + pitStopCost;

            minTimesCurrentLap[j] = std::min(optionKeepSameTire, optionChangeTire) + lapDurations[i][j];
        }
    }

    // Thời gian ngắn nhất để hoàn thành toàn bộ cuộc đua là giá trị nhỏ nhất trong mảng của vòng cuối cùng
    int finalMinTotalTime = MAX_VAL;
    for (int j = 1; j <= tireCount; ++j) {
        finalMinTotalTime = std::min(finalMinTotalTime, minTimesCurrentLap[j]);
    }

    std::cout << finalMinTotalTime << std::endl;

    return 0;
}