Editorial for BANK - Xếp hàng gửi tiền
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Sub 1: vì ~n~ bé nên ta có thể dùng phương pháp duyệt.
- Sub 2: dùng phương pháp quy hoạch động:
- Gọi mảng ~f[i][j]~ là số tiền lớn nhất ngân hàng có thể thu được tính đến khách hàng thứ ~i~ sau một khoảng thời gian là ~j~.
- Đầu tiên ta sort lại các khách hàng theo thời gian chờ đợi tăng dần.
- Vì mỗi khách hàng thứ ~i~ có thể đợi được trong khoảng thời gian từ ~0 -> t[i]~, khi qua khoảng thời gian này thì khách hàng không gửi nữa nên ta sẽ xét các khả năng gửi tiền của khách trong khoảng thời gian này, và chọn ra giá trị lớn nhất có thể đạt được. Gọi ~j~ là biến chạy khoảng thời gian từ ~0 -> t[i]~, khi đó ta có công thức quy hoạch động là ~f[i][j] = max(f[i-1][j] , f[i-1][j-1] + a[i])~. Kết quả in ra là giá trị lớn nhất trong mảng ~f~.
Comments