Question

Có N người xếp hàng mua vé. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho người thứ i là ti. Mỗi người cần mua một vé nhưng được quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ. Người thứ i nhận mua hộ vé cho người thứ i+1 thì thời gian mua vé cho 2 người là ri. Tìm phương án sao cho N người đều có vé với thời gian ít nhất.

Dữ liệu vào từ file văn bản TICK.INP

• Dòng thứ nhất ghi số nguyên dương N (1
• Dòng thứ hai ghi N số nguyên dương t1, t2, ..., tn
• Dòng thứ ba ghi N-1 số r1, r2, ..., rn-1

Kết quả ghi ra file TICK.OUT

• Dòng thứ nhất ghi tổng thời gian phục vụ bán vé
• Dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng (nếu không có ai cần phải rời khỏi hàng thì qui ước ghi số 0)

Ví dụ

TICK.INP	TICK.OUT
5 2 5 7 8 4 3 9 10 10	17 2 4

Answer 1

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.\)