Dữ liệu: Vào từ tệp văn bản BUS.INP Dòng đầu tiên ghi số N. Dòng thứ hai ghi 9 số nguyên dương là giá tiền tương ứng của các đoạn 1, 2, …, 9 km. Kết quả: Ghi ra tệp văn bản BUS.OUT gồm một số nguyên duy nhất là số tiền ít

2025-02-24 17:05:29

Dữ liệu: Vào từ tệp văn bản BUS.INP Dòng đầu tiên ghi số N. Dòng thứ hai ghi 9 số nguyên dương là giá tiền tương ứng của các đoạn 1, 2, …, 9 km. Kết quả: Ghi ra tệp văn bản BUS.OUT gồm một số nguyên duy nhất là số tiền ít nhất phải trả. Ví dụ: BUS.INP 5 12 19 31 40 61 65 69 79 90 BUS.OUT 50 Code bằng c++ , không dùng vector và các full test đều đúng

Câu trả lời này dùng AI, hãy kiểm tra lại trước khi sử dụng

```cpp
#include
#include
#include

using namespace std;

int main() {
ifstream input("BUS.INP");
ofstream output("BUS.OUT");

int N;
input >> N;
int price[9];
for (int i = 0; i < 9; i++) {
input >> price[i];
}

int dp[1001]; // Khai báo mảng dp có kích thước tối đa 1000km
for (int i = 1; i <= N; i++) {
dp[i] = INT_MAX; // Khởi tạo giá trị lớn nhất
}
dp[0] = 0; // Không tốn tiền khi không di chuyển

for (int i = 1; i <= N; i++) {
for (int j = 0; j < 9; j++) {
if (i >= (j + 1)) {
dp[i] = min(dp[i], dp[i - (j + 1)] + price[j]);
}
}
}

output << dp[N]; // Ghi kết quả vào tệp
input.close();
output.close();

return 0;
}
```

Giải thích chi tiết:

Chương trình này sử dụng phương pháp quy hoạch động để tính toán số tiền chi phí thấp nhất để đi một khoảng cách N km bằng xe buýt, với giá vé cho từng đoạn đường từ 1 đến 9 km đã được cung cấp.

1. Khởi tạo: Đầu tiên, chương trình đọc từ tệp `BUS.INP`, bao gồm số km N và giá vé cho từng đoạn. Mảng `dp` được sử dụng để lưu trữ chi phí tối thiểu cho từng khoảng cách từ 0 đến N.

2. Khởi tạo giá trị: Tất cả các giá trị trong mảng `dp` (trừ dp[0]) đều được khởi tạo thành một giá trị lớn nhất (`INT_MAX`), trong khi dp[0] được đặt bằng 0 vì không tốn tiền khi không di chuyển.

3. Tính toán: Sử dụng hai vòng lặp:
- Vòng lặp ngoài chạy từ 1 đến N (khoảng cách cần tính toán).
- Vòng lặp trong kiểm tra từng đoạn từ 1 đến 9 km (vị trí j) để cập nhật giá trị dp cho khoảng cách hiện tại. Nếu khoảng cách `i` lớn hơn hoặc bằng `j + 1`, thì chương trình tính toán chi phí mới bằng cách so sánh giữa chi phí hiện tại và chi phí của đoạn trước cộng với giá vé của đoạn hiện tại.

4. Kết quả: Cuối cùng, chương trình ghi kết quả chi phí tối thiểu vào tệp `BUS.OUT`.

Cách tiếp cận này đảm bảo rằng tất cả các cách kết hợp của các đoạn đường được xem xét, và do đó tìm ra số tiền ít nhất có thể phải trả để di chuyển N km.

Đăng phản hồi