小暘教授非常愛吃拉麵,大家都叫他拉麵小暘,並且他有一些神奇的體質,會使得他體內 累積的拉麵量越多 IQ 越高。為了維持他無人能比的強度,小暘教授需要有足夠的錢負擔 他的拉麵費用(其實是他私心不想錯過任何限定款的拉麵)。國立拉麵大學(簡稱 NRU, National Ramen University)得知了小暘教授的現況,也同時需要小暘教授的天才神腦,因此 NRU 主動提供了小暘教授一堆工作機會。 小暘教授雖然是教授,不過他不是超人,不能一次同時做兩個工作。但是小暘教授是強 人,能夠在一份工作結束後馬上做另一份工作。嚴謹的說,將每一個工作的工作時間視為 一個開區間,一份工作行事曆若是合法的,則工作表上任兩個工作的工作時間不得重疊。 每個工作有三個重要資訊,分別是開始時間、結束時間以及收益。現在你是小暘教授的學 徒、秘書兼碼農,作為一個稱職的秘書,你需要幫他排一份合法的行事曆。 請幫幫小暘教授求出:在合法的工作行事曆下,所能賺取金錢的最大值。
第一行有一個正整數 N,代表小暘教授現在有多少份 NRU 工作機會。 接下來N行,每行有三個整數 ai, bi, ci,分別代表第 i 份工作的開始時間、結束時間和總收益。 其中對所有的 i,保證 ai < bi。
只有一行,包含一個正整數 M,代表合法工作下所能賺到的金錢的最大值。
//case 1 5 0 5 1 5 7 2 7 9 3 0 6 4 7 10 10 //case 2 7 0 3 10 1 4 9 0 1 2 10 18 9 3 5 2 19 50 1 19 51 2 //case 3 7 0 3 10 2 4 9 0 1 2 10 18 9 3 5 2 19 50 1 19 2000 3
//case 1 14 //case 2 23 //case 3 24
0 ≤ N ≤ 5 ⋅ 105
對所有 i = 1, . . . , N, 0 ≤ ai, bi ≤ 5 ⋅ 105
0 < ci < 231
#2020/08/26:測資已修正
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |