Mua vé
Xem dạng PDF
Gửi bài giải
Điểm:
15,00 (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:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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 ti 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à ri.
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 \le N \le 10^5)~.
- Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. ~(1 \le t_i \le 30000)~
- Dòng thứ ba ghi N - 1 số nguyên dương ~r_1, r_2, ..., r_{N - 1}. (1 \le r_i \le 30000)~
Output
- Gồm một dòng duy nhất là đáp án cần tìm
Examples
Input
5
2 5 7 8 4
4 9 10 10
Output
18
Input
4
5 7 8 4
50 50 50
Output
24
Bình luận
HINT:
ChO aI ChƯa lÀm ĐưỢC hOặC ĐaNG BÍ ahihihi :))
Đầu tiên ta đặt 2 bài toán cơ sở là:
Bài toán cơ sở 1: $$dp[0] = t[0]$$ Bởi vì người thứ nhất không thể nhờ ai mua dùm cả, thế nên bài toán cơ sở đầu tiên sẽ bằng thời gian người thứ nhất mua vé
Bài toán cơ sở 2: $$dp[1] = min(t[0] + t[1], r[0])$$ Vì sao mình phải lấy min của tổng thời gian 2 người mua vé đầu tiên và thời gian để người thứ i mua vé cho người thứ i + 1 là r[i]. Vì để lấy thời gian phục vụ bán vé nhỏ nhất (nếu như t[0] + t[1] < r[0] thì lấy r[0] và ngược lại)
Và cuối cùng công thức truy hồi của bài me vúa này là (i bắt đầu từ 2 vì ta lấy và tính 2 thời gian trước đó rồi hihi): $$dp[i] = min(dp[i - 2] + r[i - 1], dp[i - 1] + t[i])$$ Còn vì sao như vậy thì nháp ra giấy xong ngẫm lại là ra à ahihi
Kem đánh răng P/S: VÀ vì cái hint này là đc thầy Sơn giảng lại cho mình và mình hiểu lại theo cách hiểu của mình và viết lên đây nếu ai thấy sai sai chỗ nào thí cứ comment phía dưới cho mình biết cái nhé và cuối cùng Like anh Subcribe for my channel!
who ask u >:)
lam nhu t de hieu hon
Tin nhắn này đã bị xóa
skibidibidi dop dop dop dop ya ya
click here to earn 1000$