Giải
Gọi f[i] là tổng thời gian mua vé nhỏ nhất tính từ người 1..người i
Ta có công thức truy hồi:
\(f_i=min(f_{i-1}+t_i,f_{i-2}+t_{i-1})\)
Chương trình sau dùng hai biến f1, f2 để lưu kết quả bài toán con.
Chương trình
\(const\)
\(fin='tick.inp';fon='tick.out';\)
\(maxn=60000;\)
\(var\)
\(n,i:longint;\)
\(t,r,f:array[1..maxn] \ of \ longint;\)
\(f1,f2,tam:longint;\)
\(function \ \ min(a,b:longint):longint;\)
\(var \ x:longint;\)
\(begin\)
\(x:=a;\)
\(if \ b<x \ then \ x:=b;\)
\(exit(x);\)
\(end;\)
\(begin\)
\(assign(input,fin);reset(input);\)
\(assign(output,fon);rewrite(output);\)
\(read(n);\)
\(for \ i:=1 \ to \ n \ do \ read(t[i]);\)
\(for \ i:=1 \ to \ n-1 \ do \ read(r[i]);\)
\(f1:=t[1];\)
\(f2:=min(t[1]+t[2],r[1]);\)
\(for \ i:=3 \ to \ n \ do\)
\(begin\)
\(tam:=f2;\)
\(f2:=min(f2+t[i],f1+r[i-1]);\)
\(f1:=tam;\)
\(end;\)
\(writeln(f2);\)
\(close(input);close(output);\)
\(end.\)