Editorial for Mua vé tàu hoả


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.