Xếp hàng mua vé

Điểm: 0,05 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

VNOI Marathon '08 - Practice Round

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ ~1~ đến ~N~ theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_{i}~ là thời gian cần thiết để người ~i~ mua xong vé cho mình. Nếu người ~i+1~ rời khỏi hàng và nhờ người ~i~ mua hộ vé thì thời gian để người thứ ~i~ mua được vé cho cả hai người là ~r_{i}~.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

Dòng đầu tiên chứa số ~N~ ~(1 \leq N \leq 60000)~.
Dòng thứ hai ghi ~N~ số nguyên dương ~t_{1}~, ~t_{2}~, ..., ~t_{N}~. ~(1 \leq t_{i} \leq 30000)~
Dòng thứ ba ghi ~N-1~ số nguyên dương ~r_{1}~, ~r_{2}~, ..., ~r_{N-1}~. ~(1 \leq r_{i} \leq 30000)~

Output

In ra tổng thời gian phục vụ nhỏ nhất.

Sample Input

5
2 5 7 8 4
4 9 10 10

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

-12

khiemgia1105 đã bình luận lúc 4, Tháng 10, 2024, 7:48

Mn đăng kí khoắ học ở prf mình nhé, cam kết có giải

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-12
Huy_inIT đã bình luận lúc 8, Tháng 8, 2024, 12:30
** #include <bits/stdc++.h>

define MASK(i) (1LL << (i))

define all(x) x.begin(), x.end()

define setpr(x) cout<<setprecision(x)<<fixed>
define fastbuild ios::syncwithstdio(false); cin.tie(0);

define whatIs(x) cerr << "Line " << LINE << ": " << #x << " = " << (x) << endl

typedef long long ll; using namespace std;

signed main() { int n; cin >> n; vector<int> t(n+1); vector<int> r(n+1); for(int i=1; i<=n; i++) cin >> t[i]; for(int i=1; i<=n; i++) cin >> r[i];

/* moi nguoi can mua 1 ve, nguoi bán hàn được phép bán tối đa 2 vé người i mua tốn t[i] người i+1 rời khỏi hàng và nhờ người i mua hộ vé tốn r[i] thời gian dp[i]: tổng thời gian bé nhất để mua kể từ người thứ 1 tới người thứ 1 dp[1] = a[1] dp[2] = min(dp[1] + a[2], r[1]) dp[i] = min(dp[i-1] + a[2], dp[i-2] + r[i-1]) */ int dp[60010]; memset(dp, 10000000, sizeof(int)); dp[1] = t[1]; dp[2] = min(dp[1] + t[2], r[1]); for(int i=3; i<=n; i++) { dp[i] = min(dp[i-1] + t[i], dp[i-2] + r[i-1]); } cout << dp[n]; return 0;

}
</fixed>
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

MalazeKL đã bình luận lúc 2, Tháng 7, 2024, 18:04 ← sửa 6 →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

MalazeKL đã bình luận lúc 2, Tháng 7, 2024, 18:05 ← chỉnh sửa →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-24

hieuz08 đã bình luận lúc 11, Tháng 6, 2024, 2:12

ĐỊt mẹ thg Minh Hiếu 3==Đ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

nhanphamj đã bình luận lúc 27, Tháng 7, 2024, 14:24

ko chửi bạn

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-16

a3k27_13_nguyenvantai đã bình luận lúc 30, Tháng 3, 2024, 15:48

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

thanhhoang đã bình luận lúc 23, Tháng 1, 2024, 19:01

Quy Hoạch Động f[n] = t[n]; f[i] = min( t[i] + f[i + 1], r[i] + f[i + 2] ) ( i : n - 1 --> 1 )

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

thanhhoang đã bình luận lúc 23, Tháng 1, 2024, 19:02

=> f[1]

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-16

Cuunon311 đã bình luận lúc 8, Tháng 10, 2023, 4:14

uk

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-39

kevininyourarea đã bình luận lúc 14, Tháng 4, 2023, 1:46

để cmt ở đây để xin upvote :>

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-35

NguyenDongAnh đã bình luận lúc 9, Tháng 9, 2022, 14:29 ← chỉnh sửa →

Bài Hay nhỉ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

23

sickboy1368 đã bình luận lúc 11, Tháng 1, 2022, 6:46

quy hoạch động so sánh ( f[i-1] + t[i] ) với ( f[i-2] + r[i-1] )

-55

nictysine1 đã bình luận lúc 16, Tháng 2, 2022, 8:41 ← chỉnh sửa →

upvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-363

ltphuc đã bình luận lúc 20, Tháng 4, 2021, 3:45

Em la newbie moi bat dau hoc tin, ai co the cho em xin code voi a, em cam on moi nguoi nhieu

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-149

nngovannhhungg đã bình luận lúc 15, Tháng 1, 2022, 7:19

cần thêm 2 người downvote nx cho chẵn :))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-161

manhtuan22007 đã bình luận lúc 27, Tháng 11, 2021, 12:54

cần thêm 1 người downvote nx cho chẵn :))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-158

ekhoavvdd đã bình luận lúc 22, Tháng 11, 2021, 16:31

cần thêm 1 người downvote nữa cho chẵn :))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.