|
|
Từ tập các bài có trên SPOJ (oi)
2333. Billboard painting
Mã bài: NKPANO
|
Một đội thợ sơn gồm K người cần thực hiện sơn một bức pano dành cho quảng cáo có dạng một hình chữ nhật kích thước 1xN được chia ra làm N vạch kích thước 1x1. Các vạch được đánh số từ trái
sang phải bắt đầu từ 1. Thợ i (1 ≤ i ≤ K) đang ngồi trước vạch Si của pano và anh ta chỉ có thể sơn một dãy các vạch liên tiếp của pano trong đó phải có vạch Si. Thợ i chỉ có thể
sơn không quá Li vạch và tiền công mà anh ta nhận được từ việc sơn một vạch là Pi . Mỗi vạch được sơn bởi không quá một thợ.
Yêu cầu: Tìm cách phân công thợ sơn các vạch của pano sao cho tổng tiền công của tất cả các thợ nhận được là lớn nhất.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương N, K (N ≤ 16000; K ≤ 100).
- Dòng thứ i trong số K dòng tiếp theo chứa ba số nguyên Li , Pi, Si (i = 1, 2, … K) được ghi cách nhau bởi dấu cách (1 ≤ Pi ≤ 10000, 1 ≤
Li , Si ≤ N ).
Chú ư:
- Cách phân công tìm được không nhất thiết phải đảm bảo sơn hết tất cả các vạch của pano.
- Nếu thợ i không sơn vạch nào cả thì việc sơn vạch Si có thể được phân công cho thợ khác.
- Các số S1, S2, . . . SK giả thiết là khác nhau từng đôi.
Kết quả
Ghi ra tổng tiền công nhận được từ cách phân công thợ tìm được.
Ví dụ
Dữ liệu:
8 4
3 2 2
3 2 3
3 3 5
1 1 7
Kết qủa
17
(Cách phân công: Thợ 1 sơn các vạch 1, 2; thợ 2 sơn các vạch 3, 4; thợ 3 sơn các vạch 5, 6, 7; thợ 4 không sơn vạch nào).
| Được gửi lên bởi: | Ngô Minh Đức |
| Ngày: | 2008-01-13 |
| Thời gian chạy: | 1s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | Prof. Nguyen Duc Nghia |
|
|
|
|
