NKPANO - Billboard painting

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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:Jimmy
Ngày:2008-01-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Prof. Nguyen Duc Nghia

hide comments
2020-08-23 15:25:04
https://pastebin.com/nD2Zw2iQ
- Đệ thầy Hoàng -
2016-12-23 08:54:18 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/549/nkpano-spoj/
2016-09-08 11:45:46
I'm allowed to delete the post and use html code here.|
2015-07-25 13:08:27 there's no salvation for me...
làm IT time nhỏ vãi =)))
2014-12-23 13:53:08 Nghiêm Vãn Long
cho e xin bafi tham khao, gmail : vochandoiqua@gmail.com
2014-08-06 01:47:57 ■■‡[ND] Bee Sociu■■‡
Please be careful, leave short comments only. Don't spam here.
2014-06-30 05:54:21 ๖ۣۜPublic °°
Bài này duyệt là được 20% nha các bạn. ai muốn tham khảo có thể gửi mail cho t. :v

Last edit: 2014-06-30 11:28:21
2014-05-07 20:52:25 an IM3 Ex-Member of Bit
Test yếu, một số chương trình sai vẫn AC.
2014-04-17 07:17:16 Trần Duy Lực
Quy hoạch động .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.