//
you're reading...
Bài tập huấn luyện, Chủ đề quy hoạch động, Lập trình Pascal nâng cao, Đề thi HSG quốc gia VNOI

Chuyên đề Quy hoạch động -Vòng Quanh Thế Giới

[Nguồn] []


Đề bài


(Đề Thi Học Sinh Giỏi Quốc Gia 2000-2001 – Bảng A )

Trên tuyến đường của xe chở khách du lịch vòng quanh thế giới xuất phát từ bến X có N khách sạn đánh số từ 1 đến N theo thứ tự xuất hiện trên tuyến đường , trong đó khách sạn N là địa điểm cuối cùng của tuyến đường mà tại đó xe bắt buộc phải dừng . Khách sạn I cách địa điểm xuất phát Ai Km (I=1,2,..N);A1<A2<…<AN

Để đảm bảo sức khoẻ cho khách hàng , theo tính toán của các nhà chuyên môn, sau khi đã chạy được P (Km) xe nên dừng lại cho khách nghỉ ở khách sạn . Vì thế ,nếu xe dừng lại cho khách nghỉ ở khách sạn sau khi đã đi được Q(Km) thì lái xe phải trả một lượng phạt là : (Q-P)^2  .

Ví Dụ :

Với N=4 ,P=300,A1=250, A2=310, A3=550 ,A4=590 .Xe bắt buộc phải dừng lại ở khách sạn 4 là địa điểm cuối cùng của hành trình . Nếu trên đường đi lái xe chỉ dừng lại tại khách sạn thứ 2 thì lượng phạt phải trả là :

(310-300)^2+((590-310)-300)^2=500

Yêu Cầu :  Hãy xác định  xem trên tuyến đường đến khách sạn N , xe cần dừng lại nghỉ ở những khách sạn nào để tổng lượng phạt mà lái xe phải trả là nhỏ nhất.

Dữ Liệu :  Vào từ File văn bản có tên Bai5.Inp :

  • Dòng đầu tiên chứa số nguyên dương N(N<=10000);
  • Dòng thứ hai chứa số nguyên dương P (P<=500);
  • Dòng thứ ba chứa các số nguyên dương A1,A2,A3,..An ( hai số liên tiếp cách nhau ít nhất bởi 1 dấu cách ) ( Ai<=2000000 ,i=1,2,..N)

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

  • Dòng đầu tiên ghi Z là lượng phạt mà lái xe phải trả ;
  • Dòng thứ hai ghi K là tổng sô khách sạn mà lái xe cần dừng lại cho khách nghỉ;
  • Dòng thứ ba chỉ chứa chỉ số của K khách sạn mà xe dừng lại cho khách nghỉ ( Trong đó nhất thiết phải có khách sạn thứ N)

Ví Dụ:

BAI5.INP                                                                          BAI5.OUT

4 300 250 310 550 590                                                     500 2 2 4

 


Hướng dẫn


Gọi Mind[i] là lượng phạt ít nhất nếu người lái xe dừng lại địa điểm i . Chúng ta sẽ có công thức truy hồi :

                                Mind[i]:=MinMind[j]+sqr(a[i]-a[j]-p); j=1,..i-1

Tuy nhiên bài toán này chưa phải là đã được giải quyết. Bởi vì nó còn quá nhiều vấn đề cần giải quyết khác :

  • Lượng phạt có thể rất lớn , vượt quá longint mà nếu chứa trong real thì sẽ không thể lưu được mảng có 10000 phần tử . Chính vì thế chúng ta cần giải quyết tốt dữ liệu bài toán này .
  • Nếu N=10000 thì chương trình sẽ phải chạy : (9999+1)*9999/2 . Tức là rất lâu .

Chính vì thế các bạn cần phải hoàn thành một cách đúng đắn các điều kiện trên .


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

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: