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
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é
#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<<"\n";
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]<<"\n";
vet(n);
}
