Hướng dẫn giải của Mua vé tàu hoả
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=100011; var a,b:array[1..maxn] of int64; s,f,n:longint; l,c:array[1..3] of int64; procedure rf; var i:longint; begin for i:=1 to 3 do read(l[i]); for i:=1 to 3 do read(c[i]); readln; readln(n); readln(s,f); for i:=2 to n do readln(a[i]); end; procedure pr; var i,j,k,t:longint; begin for i:=1 to n do b[i]:=maxlongint*10000; b[s]:=0; for j:=s+1 to f do for i:=j-1 downto s do begin if a[j]>a[i]+l[3] then break; for k:=1 to 3 do if (a[j]-a[i]<=l[k]) and (b[j]>b[i]+c[k]) then begin b[j]:=b[i]+c[k]; break; end; end; end; procedure wf; begin write(b[f]); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 100005 typedef long long LL; int l[3], c[3], n, s, f; //a[i] = k/c giua ga 1 va ga i long long d[N], a[N]; void enter() { scanf("%d%d%d%d%d%d%d%d%d",l,l+1,l+2,c,c+1,c+2,&n,&s,&f); if(s>f) swap(s,f); fo(i,2,n) scanf("%lld",a+i); } //LL min(LL a, LL b) { return a < b ? a : b; } void process() { fill(d+s+1, d+n+1, LLONG_MAX-2*INF); fo(i,s+1,f) { rep(k,3) { int p = lower_bound(a+1, a+n+1, a[i] - l[k]) - a; d[i] = min(d[i], d[p] + c[k]); } } cout << d[f] << endl; //cout << *min_element(d+f, d+n+1) << endl; } int main() { //freopen("input.txt", "r", stdin); enter(); process(); return 0; }
Code mẫu của ladpro98
program qbticket; uses math; const fi=''; maxN=100005; oo=trunc(1e18); var a,f:array[1..maxN] of int64; n,st,fin,l1,l2,l3,c1,c2,c3:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,l1,l2,l3,c1,c2,c3); readln(inp,n); readln(inp,st,fin); a[1]:=0; for i:=2 to n do readln(inp,a[i]); close(inp); end; function find(r:longint;key:int64):longint; var l,m,k:longint; begin l:=st; while l<=r do begin m:=(l+r) shr 1; if a[m]>=key then begin k:=m; r:=m-1; end else l:=m+1; end; exit(k); end; procedure dp; var i,x,y,z:longint; begin f[st]:=0; for i:=st+1 to fin do begin x:=find(i,a[i]-l1); y:=find(i,a[i]-l2); z:=find(i,a[i]-l3); f[i]:=oo; if x<>i then f[i]:=min(f[i],f[x]+c1); if y<>i then f[i]:=min(f[i],f[y]+c2); if z<>i then f[i]:=min(f[i],f[z]+c3); end; end; begin input; dp; write(f[fin]); end.
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=100111; oo=1000000000000000001; var f1,f2:text; n,l1,l2,l3,c1,c2,c3,s,t,start,target:int64; vt,ind:array[1..MAXN] of int64; d:array[1..MAXN] of int64; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,l1,l2,l3,c1,c2,c3); read(f1,n); read(f1,s,t); for i:=2 to n do read(f1,vt[i]); for i:=1 to n do ind[i]:=i; end; procedure swap(var a,b:int64); var temp:int64; begin temp:=a; a:=b; b:=temp; end; procedure sort(l,r:int64); var i,j,mid:int64; begin i:=l; j:=r; mid:=vt[l+random(r-l+1)]; repeat while vt[i]<mid do inc(i); while vt[j]>mid do dec(j); if i<=j then begin swap(vt[i],vt[j]); swap(ind[i],ind[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure solve; var i1,i2,i3:int64; i:longint; begin // for i:=2 to n do if ind[i]=s then start:=i; // for i:=2 to n do if ind[i]=t then target:=i; start:=s; target:=t; if start>target then swap(start,target); d[start]:=0; i1:=start; i2:=start; i3:=start; for i:=1+start to target do begin d[i]:=oo; //Cap nhat theo loai 1 while (vt[i]-vt[i1]>l1) do inc(i1); d[i]:=min(d[i],d[i1]+c1); //Cap nhat theo loai 2 while (vt[i]-vt[i2]>l2) do inc(i2); d[i]:=min(d[i],d[i2]+c2); //Cap nhat theo loai 3 while (vt[i]-vt[i3]>l3) do inc(i3); d[i]:=min(d[i],d[i3]+c3); end; end; procedure ans; begin writeln(f2,d[target]); end; begin openF; inp; // sort(1,n); solve; ans; closeF; end.
Code mẫu của ll931110
Program QBTICKET; Const input = ''; output = ''; maxn = 100000; maxl = 1000000000; maxv = maxn * maxl; Var l,c: array[1..3] of longint; heap: array[1..maxn] of longint; a,d: array[1..maxn + 1] of int64; n,s,f,nHeap: longint; Procedure init; Var fi: text; i,t: longint; Begin Assign(fi, input); Reset(fi); Readln(fi,l[1],l[2],l[3],c[1],c[2],c[3]); Read(fi, n, s, f); If s > f then Begin t:= s; s:= f; f:= t; End; a[1]:= 0; For i:= 2 to n do readln(fi, a[i]); a[n + 1]:= maxv; Close(fi); End; Procedure update(v: longint); Var child,parent: longint; Begin inc(nHeap); child:= nHeap; parent:= child div 2; While (parent > 0) and (heap[parent] > v) do Begin heap[child]:= heap[parent]; child:= parent; parent:= child div 2; End; heap[child]:= v; End; Function pop: longint; Var r,c,v: longint; Begin pop:= heap[1]; v:= heap[nHeap]; dec(nHeap); r:= 1; While r * 2 <= nHeap do Begin c:= r * 2; If (c < nHeap) and (heap[c + 1] < heap[c]) then inc(c); If heap[c] >= v then break; heap[r]:= heap[c]; r:= c; End; heap[r]:= v; End; Procedure solve; Var i,u,v: longint; Begin nHeap:= 0; For i:= 1 to n do d[i]:= maxv; d[s]:= 0; update(s); Repeat u:= pop; v:= u; For i:= 1 to 3 do Begin While (a[u] + l[i] >= a[v]) and (v <= f) do inc(v); dec(v); If d[v] = maxv then update(v); If d[v] > d[u] + c[i] then d[v]:= d[u] + c[i]; End; Until nHeap = 0; End; Procedure printresult; Var fo: text; Begin Assign(fo, output); Rewrite(fo); Writeln(fo, d[f]); Close(fo); End; Begin init; solve; printresult; End.
Code mẫu của skyvn97
#include<algorithm> #include<cstdio> #include<cstring> #include<iostream> #define MAX 100100 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) using namespace std; typedef long long ll; ll len[3],cost[3],d[MAX]; ll f[MAX]; int n,s,t; inline void minimize(ll &x,const ll &y) { if (x>y) x=y; } void init(void) { REP(i,3) scanf("%lld",&len[i]); REP(i,3) scanf("%lld",&cost[i]); scanf("%d%d%d",&n,&s,&t); FOR(i,2,n) scanf("%lld",&d[i]); if (s>t) swap(s,t); } void optimize(void) { memset(f,0x3f,sizeof f); f[s]=0; int id[3]; REP(i,3) id[i]=s; FOR(i,s+1,t) REP(j,3) { while (id[j]<i && d[id[j]]<d[i]-len[j]) id[j]++; if (id[j]<i) minimize(f[i],f[id[j]]+cost[j]); } printf("%lld",f[t]); } int main(void) { init(); optimize(); return 0; }
Bình luận