//
you're reading...
00 - Chủ đề chung, Chủ đề quy hoạch động, Lập trình Pascal nâng cao

Chuyên đề Quy hoạch động – Dạo chơi bằng xe buýt

[Nguồn] []


Đề bài


Trên một tuyến đờng ở thành phố du lịch nổi tiếng X có ô tô buýt công cộng phục vụ việc đi lại của du khách . Bến xe buýt có ở từng Km của tuyến đờng . Mỗi lần đi qua bến xe đều đỗ cho du khác lên xuống . Mỗi bến đều có xe xuất phát từ nó , nhng mỗi xe chỉ chạy không quá B Km kể từ bến xuất phát của nó . Hành khách khi đi xe sẽ phải trả tiền cho độ dài đoạn đờng mà họ ngồi trên xe. Cớc phí cần trả để đi đoạn đờng độ dài i là Ci (I=1,2,..B) . Một du khách xuất phát từ một bến nào đó muốn đi dạo L Km trên tuyến đờng nói trên . Hỏi ông ta phải lên xuống xe nh thế nào để tổng số tiền phải trả cho chuyến dạo chơi bằng xe buýt là nhỏ nhất .

Dữ Liệu : Vào Từ File :   Bus.Inp

  • Dòng đầu tiên chứa 2 số nguyên dơng B,L (B<=100,L<=10000)
  • Dòng thứ hai chứa B số Nguyên dơng C1,C2,..Cn , đợc ghi cách nhau bởi dấu trắng

Kết Quả : Ghi ra File Văn Bản :     Bus.Out

  • Dòng đầu tien ghi chi phí tìm đợc ,và số lần xuống xe K .
  • Dòng tiếp theo ghi K số là độ dài của các đoạn đờng của K lần ngồi xe. “

Ví Dụ:

BUS.INP                                                                                        BUS.OUT

10 15 12 21 31 40 49 58 69 79 90 101                                      147 3 3  6  6


Hướng dẫn


Gọi Mind[I] Là số tiền ít nhất cần trả khi ngời đó cần đi I Km . Chúng ta sẽ có công thức quy hoạch động :

Mind[I]:=MinMind[I-J]+A[J]; J: J<=I ;

Giá trị Mind[L] là gía trị cần tính .


Lời giải – Chương trình


b

b


Tài liệu tham khảo


  1. a
  2. a

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: