自從華山論劍聲名大噪之後,很多人都想參加,但 $20$ 年辦一次實在太久了,五輪奧運都跑 $5$ 趟了,於是各地都紛紛舉辦華山論劍,往往同一天就有很多場。每一場都有自己的開始時間與結束時間,參加者必須全程在場,所以兩場的時間如果有重疊就不能同時參加。
令狐沖本來想參加最多場來盡速累積經驗值,但後來他發現有很多場次能獲得的經驗值很少,參加了反而浪費時間,
現在要請你幫忙計算最多可以得到的經驗值總和。
請注意,所挑選活動必須完全不重疊,兩場活動只在端點重疊也是不可以同時參加的,也就是說前一場的結束時間必須小於下一場的開始時間。
第一行是一個正整數 $n$,代表一共舉辦了 $n$ 場華山論劍,
接下來 $n$行,每行有三個非負整數 $s$、$t$ 與 $e$,代表這場活動時間區間是$[s, t]$,而可以得到的經驗值是 $e$,兩數字間以空白間格。
$n \leq 10^5, s < t < 10^9$,答案不超過 $10^9$。
最大可能經驗值總和。
3 1 2 1 2 3 3 3 4 1
3
3 1 2 2 2 3 3 3 4 2
4
挑選 $[2,3]$,得到經驗值 $3$。
挑選 $[1,2]$ 與 $[3,4]$,得到經驗值 $2+2=4$。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |