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 ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | const fi='; fo='; nmax=10000; vc=high(int64); type data=longint; var f:text; tr:array[0..nmax+1] of data; B,a:array[0..nmax+1] of int64; n,p:data; KQ:array[1..nmax] of data; spt:data; procedure docfile; var i,x:data; begin assign(f,fi); reset(f); read(f,n,p); for i:=1 to n do begin read(f,x); a[i]:=x; end; close(f); end; procedure QHD; var i,j:data; vt,v:data; gtmin,x:int64; begin b[0]:=0; A[0]:=0; for i:=1 to n do begin gtmin:=vc; for j:=0 to i-1 do begin if (gtmin>=b[j]+sqr(a[i]-a[j]-p)) then begin vt:=j; gtmin:=b[j]+sqr(a[i]-a[j]-p); end; end; b[i]:=gtmin; tr[i]:=vt; end; assign(f,fo); rewrite(f); writeln(f,b[n]); spt:=1; kq[1]:=n; v:=n; while tr[v]<>0 do begin inc(spt); kq[spt]:=tr[v]; v:=tr[v]; end; writeln(f,spt); for i:=spt downto 1 do write(f,kq[i],' '); close(f); end; begin docfile; QHD; end. |
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é
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<bits/stdc++.h> using namespace std; #define N 10005 #define ll long long #define sqr(a) a*a const ll oo=LLONG_MAX; int n,a[N],p,tr[N],dem=0,kq[N]; ll d[N]; void vet(int u) { while(u) { dem++; kq[dem]=u; u=tr[u]; } cout<<dem<<"
"; for(int i=dem;i;i--) cout<<kq[i]<<" "; } int main() { // freopen("TOURISM.INP","r",stdin); //freopen("TOURISM.OUT","w",stdout); ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>p; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { ll dmin=oo; int jmin=0; for(int j=0;j<i;j++) if(dmin>=d[j]+(ll)(a[i]-a[j]-p)*(a[i]-a[j]-p)) { dmin=d[j]+(ll)(a[i]-a[j]-p)*(a[i]-a[j]-p); jmin=j; } d[i]=dmin; tr[i]=jmin; } cout<<d[n]<<"
"; vet(n); } |
