Tuyến xe bus T6 nối Quy Nhơn – Tây Sơn – Vĩnh Thạnh được tổ chức theo
cách sau đây: Xe buýt có thể chạy không dừng theo các đoạn 1, 2, 3, …, 9 km. Với
mỗi đoạn

Question

Tuyến xe bus T6 nối Quy Nhơn – Tây Sơn – Vĩnh Thạnh được tổ chức theo
cách sau đây: Xe buýt có thể chạy không dừng theo các đoạn 1, 2, 3, …, 9 km. Với
mỗi đoạn trong 9 đoạn này có giá vé cố định cho trong một bảng.
Ví dụ như bảng giá vé sau:
Độ dài đoạn đường đi Giá vé
1 km| 12
2 km| 19
3 km| 31
4 km| 40
5 km| 61
6 km| 65
7 km| 69
8 km| 79
9 km| 90
Một hành khách muốn đi N km bằng xe buýt (1 ≤ N ≤ 1000).
Yêu cầu: Hãy viết chương trình để hành khách có thể chọn những khoảng
cách dừng xe hợp lý để hành trình phải trả tiền ít nhất.
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
giúp giải bài này với mọi người

Daoanhviet96 · Answer

Để giải quyết bài toán này, ta có thể dùng phương pháp quy hoạch động:
- Gọi dp[i] là số tiền ít nhất để đi i km.
- Dễ dàng nhận thấy rằng dp[i] = min(dp[i-1] + a[1], dp[i-2] + a[2], ..., dp[i-9] + a[9])
$\$
Dưới đây là đoạn code tham khảo:
#include #include #define N 1005using namespace std;int n, a[10], dp[N];int main() {  cin >> n;  for (int i=1; i> a[i];  for (int i=1; i    dp[i] = min({dp[max(i-1,0)]+a[1], dp[max(i-2,0)]+a[2], dp[max(i-3,0)]+a[3],     dp[max(i-4,0)]+a[4], dp[max(i-5,0)]+a[5], dp[max(i-6,0)]+a[6], dp[max(i-7,0)]+a[7],     dp[max(i-8,0)]+a[8], dp[max(i-9,0)]+a[9]});  cout   }
$\$$\$$\color{#ffd710}{	exttt{\{}} \color{#8655d6}{	exttt{\{}}\ \ \color{#8cdcda}{	ext{Daoanhviet96}}\ \ \color{#8655d6}{	exttt{\}}} \color{#ffd710}{	exttt{\}}}$

TRẢ LỜI

TRẢ LỜI

Bạn muốn hỏi điều gì?

Tham Gia Group Dành Cho Lớp 9 - Ôn Thi Vào Lớp 10 Miễn Phí

Bạn muốn hỏi điều gì?

Tìm kiếm với hình ảnh

Hãy đăng nhập hoặc tạo tài khoản miễn phí!

Lưu vào

TRẢ LỜI

TRẢ LỜI

Bạn muốn hỏi điều gì?

Tham Gia Group Dành Cho Lớp 9 - Ôn Thi Vào Lớp 10 Miễn Phí

Bạn muốn hỏi điều gì?

Lý do báo cáo vi phạm?