P-6-16. 山寨華山論劍


提交答案

分數: 100 (部分)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型

自從華山論劍聲名大噪之後,很多人都想參加,但 20 年辦一次實在太久了,五輪奧運都跑 5 趟了,於是各地都紛紛舉辦華山論劍,往往同一天就有很多場。每一場都有自己的開始時間與結束時間,參加者必須全程在場,所以兩場的時間如果有重疊就不能同時參加。
令狐沖本來想參加最多場來盡速累積經驗值,但後來他發現有很多場次能獲得的經驗值很少,參加了反而浪費時間,
現在要請你幫忙計算最多可以得到的經驗值總和。
請注意,所挑選活動必須完全不重疊,兩場活動只在端點重疊也是不可以同時參加的,也就是說前一場的結束時間必須小於下一場的開始時間。

輸入格式

第一行是一個正整數 n,代表一共舉辦了 n 場華山論劍, 接下來 n行,每行有三個非負整數 ste,代表這場活動時間區間是[s,t],而可以得到的經驗值是 e,兩數字間以空白間格。 n105,s<t<109,答案不超過 109

輸出格式

最大可能經驗值總和。

範例輸入 1

複製
3
1 2 1
2 3 3
3 4 1

範例輸出 1

複製
3

範例輸入 2

複製
3
1 2 2
2 3 3
3 4 2

範例輸出 2

複製
4

提示

case 0:

挑選 [2,3],得到經驗值 3

case 1:

挑選 [1,2][3,4],得到經驗值 2+2=4


留言

目前沒有評論。