s796. 蜂蜜工廠 - 高中生程式解題系統

內容

蜜蜂王國裡有一間蜂蜜工廠，每個月蜂蜜工廠都會收到來自全球各地的 M（1≤M≤200000）張蜂蜜訂單。蜂蜜工廠裡只有一台蜂蜜製造機，由於蜂蜜製程極其繁複，這台機器每天最多只能製造 1 瓶蜂蜜（即一天只能處理一個訂單），且每個訂單一旦被選中，皆需要恰好 1 天的機器時間來完成。蜜蜂王國使用的是蜂元紀，所以每個月不是常見的28、29、30、31天，而是 N（1≤N≤200000）天。

對於每張訂單 i，皆有：

1. L_i（1≤L_i≤R_i）：收到訂單的日期，即該筆訂單最早能在第 L_i 天（含）開始製作。

2. R_i（L_i≤R_i≤N）：訂單截止的日期，即該筆訂單最晚必須在第 R_i 天（含）前製作完成。

3. P_i（1≤P_i≤10⁹）：完成該訂單可獲得的金幣。

而由於部分訂單的時間區間互相衝突，且機器的產能有限，蜂蜜工廠可能不能滿足所有的訂單。請你協助蜂蜜工廠設計一個製造計畫，選擇一個訂單子集並為它們分配合適的製造日期，使得工坊賺取的總酬勞（金幣總和）達到最大。

以下為一個 N = 4, M=4 的例子，我們有四張訂單：

訂單編號	可製造區間	酬勞（金幣）
1	[1, 2]	40
2	[2, 2]	10
3	[2, 3]	50
4	[1, 3]	20

如果我們選擇放棄訂單2，並將剩下的訂單如下安排，則我們可以獲得最大總酬勞（金幣總和）110。

天次	1	2	3	4	總和
訂單	訂單1 （[1, 2]）	訂單3 （[2, 3]）	訂單4 （[1, 3]）	空	-
酬勞	40	50	20	0	110

天次

總和

訂單

訂單1

（[1, 2]）

訂單3

（[2, 3]）

訂單4

（[1, 3]）

空

酬勞

110

輸入說明

第一行包含兩個正整數 N 與 M，分別代表月份的日期數與訂單總數。

接下來的 M 行，每行包含三個正整數 L_i, R_i, P_i，分別代表第 i 個訂單的開始日、截止日與酬勞。

輸出說明

請輸出一個整數，代表蜂蜜工廠能獲得的最大總酬勞。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 256 MB
不公開測資點#0 (5%): 1.0s , <10M
不公開測資點#1 (5%): 1.0s , <10M
不公開測資點#2 (5%): 1.0s , <10M
不公開測資點#3 (5%): 1.0s , <10M
不公開測資點#4 (5%): 1.0s , <10M
不公開測資點#5 (5%): 1.0s , <10M
不公開測資點#6 (5%): 1.0s , <10M
不公開測資點#7 (5%): 1.0s , <10M
不公開測資點#8 (5%): 1.0s , <10M
不公開測資點#9 (5%): 1.0s , <1K
不公開測資點#10 (5%): 1.0s , <1M
不公開測資點#11 (5%): 1.0s , <1M
不公開測資點#12 (5%): 1.0s , <1M
不公開測資點#13 (5%): 1.0s , <1M
不公開測資點#14 (5%): 1.0s , <10M
不公開測資點#15 (5%): 1.0s , <10M
不公開測資點#16 (5%): 1.0s , <10M
不公開測資點#17 (5%): 1.0s , <1M
不公開測資點#18 (5%): 1.0s , <1K
不公開測資點#19 (5%): 1.0s , <1M

提示：

標籤:

AM系列題目

出處:

[管理者：

lsstmoonis@g ... (CERE) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」