Chào mừng bạn đến với Selfomy Hỏi Đáp, hãy Hỏi bài tập hoặc Tham gia ngay
0 phiếu
628 lượt xem
trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)

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


1 Câu trả lời

+2 phiếu
bởi trannhat900 ● Ban Quản Trị Phó giáo sư (52.9k điểm)
được bầu chọn là câu hỏi hay nhất bởi thanhtrong ● Ban Quản Trị
 
Hay nhất

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

Các câu hỏi liên quan

+1 thích
1 trả lời 506 lượt xem
Trên hai đường thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường N điểm. Các điểm trên đường thẳng L1 được đánh ... ; tăng dần. Ví dụ: WIRES.INP WIRES.OUT 9 2 5 3 8 7 4 6 9 1 5 2 3 4 6 9
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 130 lượt xem
Một người sử dụng INTERNET đặt yêu cầu nhận thông tin về một số chủ đề khác nhau từ một số địa chỉ truy nhập. Chủ của các ... ;t nhất cần thực hiện. Ví dụ: EMAIL.INP EMAIL.OUT 7 1 3 4 3 2 2 3 4
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 690 lượt xem
Có N khối đá hình hộp chữ nhật. Người ta muốn xây một cái tháp bằng cách chồng các khối đá này lên nhau. Để đảm bảo an toàn, các khối ... 1 5 4 2 7 2 9 2 1 3 3 5 5 5 4 1 5 7 5 9 5 5 5 5 5 5 1 4 2 4 2
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
0 câu trả lời 401 lượt xem
Cách tổ chức hoạt động của các Collection Framework như List , Map, Set, Queue, Stack,..?
đã hỏi 21 tháng 12, 2020 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
0 câu trả lời 92 lượt xem
Thế nào là lập trình đối tượng? Cho biết các tính chất đặc thù của lập trình hướng đối tượng?
đã hỏi 21 tháng 12, 2020 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
0 câu trả lời 125 lượt xem
Khái niệm về Generic? Cho ví dụ và lý do sử dụng?
đã hỏi 21 tháng 12, 2020 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
4 câu trả lời 184 lượt xem
đã hỏi 10 tháng 1, 2017 trong Tin học lớp 9 bởi Mai Đức Đạt Học sinh (371 điểm)
0 phiếu
1 trả lời 310 lượt xem
Bưu cục Có một số làng nằm dọc theo một đường cao tốc. Đường cao tốc được biểu diễn bằng một trục số nguyên và vị trí mỗ ... một. Ví dụ: POST.INP POST.OUT 10 5 1 2 3 6 7 9 11 22 44 50 9 2 7 22 44 50
đã hỏi 13 tháng 7, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 215 lượt xem
Mỗi khi có trận bóng đá hay, người dân lại xếp hàng dài chờ mua vé. Nhìn dòng người xếp hàng một, rất dài, ... ;ng ấy và dãy số tự nhiên đang học có gì giống nhau nhỉ?
đã hỏi 29 tháng 4, 2022 trong Toán lớp 6 bởi botrf22501 Học sinh (299 điểm)
0 phiếu
1 trả lời 214 lượt xem
C1: VCT tính tổng các số nguyên n được nhập từ bàn phím đến khi gặp số nguyên tố thì dừng. C2:  VCT giải bài toán sau: Yêu nhau cau sáu bổ ba Ghét nhau cau sáu bổ ra làm muời Số người tính đã tám mươi, Cau mười năm quả,hỏi người gét,yêu? Tính xem có bao nhiêu người ghét,bao nhiêu người yêu? 2 bài - bạn nào làm được 1 bài tớ sẽ vẫn tick nha!!!  
đã hỏi 12 tháng 1, 2018 trong Tin học lớp 7 bởi lop6/7tk_2017 Học sinh (314 điểm)
  1. nguyenmanh04102009212

    166 Điểm

  2. tnk11022006452

    120 Điểm

  3. hoconghung031007464

    65 Điểm

Phần thưởng hằng tháng
Hạng 1: 200.000 đồng
Hạng 2: 100.000 đồng
Hạng 3: 50.000 đồng
Hạng 4-10: 20.000 đồng
Bảng xếp hạng cập nhật 30 phút một lần
...