a350: P-6-16. 山寨華山論劍
標籤 : DP
通過比率 : 12人/13人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-05-30 14:40

內容

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

輸入說明

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

輸出說明

最大可能經驗值總和。

範例輸入 #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
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
提示 :

範例一說明:挑選[2,3],得到經驗值3。
範例二說明:挑選[1,2]與[3,4],得到經驗值2+2=4。

標籤:
DP
出處:
AP325 [管理者:
haha (大學長)
]


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