Phục vụ tiệc
Đề bài
Mô tả
Paul sở hữu một công ty phục vụ tiệc và việc kinh doanh đang rất phát đạt. Công ty có đội phục vụ, mỗi đội phụ trách một bộ thiết bị phục vụ tiệc. Mỗi tuần, công ty nhận yêu cầu phục vụ cho các sự kiện khác nhau. Với mỗi yêu cầu, công ty cử một đội cùng bộ thiết bị của đội đó tới địa điểm tổ chức sự kiện. Đội phục vụ giao đồ ăn, lắp đặt thiết bị và hướng dẫn chủ tiệc cách sử dụng thiết bị và phục vụ đồ ăn. Sau sự kiện, chủ tiệc có trách nhiệm gửi trả thiết bị về công ty của Paul.
Không may, có những tuần số đội phục vụ ít hơn số yêu cầu, nên một số đội phải phục vụ nhiều hơn một sự kiện. Khi đó công ty không thể chờ chủ tiệc gửi trả thiết bị mà phải giữ đội ở lại để chuyển thiết bị tới một địa điểm khác. Công ty ước lượng chính xác được chi phí chuyển một bộ thiết bị từ một địa điểm bất kỳ tới một địa điểm bất kỳ khác.
Với các chi phí này, Paul muốn lập một kế hoạch phục vụ mọi yêu cầu sao cho tổng chi phí di chuyển thiết bị (tính cả lần di chuyển đầu tiên) là nhỏ nhất, kể cả khi điều đó có nghĩa là không dùng hết các đội hiện có. Các yêu cầu được sắp xếp tăng dần theo thời điểm diễn ra sự kiện, và được chọn sao cho với mọi , luôn đủ thời gian để chuyển thiết bị đã dùng ở yêu cầu thứ tới địa điểm của yêu cầu thứ .
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , lần lượt là số yêu cầu và số đội phục vụ.
Tiếp theo là dòng, dòng thứ chứa số nguyên. Số thứ trên dòng thứ là chi phí chuyển một bộ thiết bị từ địa điểm tới địa điểm . Công ty ở địa điểm , còn yêu cầu lần lượt ở các địa điểm tới .
Dữ liệu ra
In ra tổng chi phí di chuyển nhỏ nhất để phục vụ mọi yêu cầu. (Tổng này không tính chi phí chuyển thiết bị về lại công ty.)
Ràng buộc
- , .
- Mọi chi phí là số nguyên trong đoạn .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 40 30 40 50 10 50 |
80 | Một đội đi với chi phí , đội còn lại đi với chi phí . Tổng là . |
| 3 2 10 10 10 20 21 21 |
40 | Một đội đi với chi phí , đội còn lại đi với chi phí . Tổng là . |
Bình luận