MTTRAVEL spoj THPTCBT – Du lịch vòng quanh thế giới

các bạn có thể nộp bài tại đây: http://www.spoj.com/THPTCBT/problems/MTTRAVEL

1. Đề bài MTTRAVEL spoj

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 hành trình mà tại đó tài xế 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 tiền phạt là : (Q-P)2 . Để đảm bảo lịch trình tài xế không được dừng khi chưa chạy đủ P Km và phải dừng tại một khách sạn nào đó.

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

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. ( Ai<=2000000, i=1,2,..N)

Kết Quả

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à 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ụ

Input

4

300

250 310 550 590

Output

500

2

2 4

2. Hướng Dẫn MTTRAVEL spoj

  • Hàm mục tiêu:

Gọi F[i] là lượng phạt ít nhất nếu người lái xe dừng lại địa điểm i.

  • Bài toán cơ sở: F[0]=oo
  • Công thức truy hồi:

F[i]:=Min{F[j]+sqr(A[i]-A[j]-P)}; với mọi j=0,..i-1

3. code tham khảo MTTRAVEL spoj

a. Code pascal MTTRAVEL spoj

b. Code c++ MTTRAVEL spoj

Đây là code của bạn maithientai305, mình lấy từ tài khoản Problem setter của mình.

Mình chưa xem qua bài làm của bạn này, các bạn cân nhắc nhé

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *