e158: 星際聯邦
Tags :
Accepted rate : 7人/8人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-05-04 20:15

Content

星年 $3$∂ 年,星際間爆發了一場能源戰爭,這場戰爭將星系間的智慧生物分成了兩派。

你現在是其中一派的軍師,現在上級需要你在他的許多名單中挑出一些部隊組成一個軍隊來進攻$\zeta \eta S$;一個不錯的戰略太陽系。

一個好的軍隊需要有防護、修復、遠程、技術、後勤、娛樂、coding、動漫...等雜七雜八的屬性,而哪些部隊有這些屬性你的有良心上級已經幫你分好了,你只需要在那些名單中選出部隊組成軍隊。

近日因為某大火導致經費拮据,所以你的軍隊需要"精簡化",即是需要最小量的部隊種類數量

PS.你的上司有個奇怪的習慣,名單上的部隊編號的是連續的

 

Input

第一行有一個數字$n$,代表接下來有$n$份名單,每份名單都代表不同的屬性。

接下來有$n$行,每一行都有$a_i, b_i, c_i$,分別代表第 $i$ 個名單裡有部隊編號$a_i \sim b_i$,以及你需要在這份名單中至少選幾個部隊。

$1 <= a_i <= b_i <= 50000$

$1 <= c_i <= b_i - a_i+1$

Output

請輸出在此$n$份名單內選$c_i$個部隊,所能組成最小軍隊的大小。

Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
測資資訊:
記憶體限制: 20 MB
公開 測資點#0 (9%): 1.0s , <1K
公開 測資點#1 (9%): 1.0s , <1K
公開 測資點#2 (9%): 1.0s , <1K
公開 測資點#3 (9%): 1.0s , <1M
公開 測資點#4 (9%): 1.0s , <1M
公開 測資點#5 (9%): 1.0s , <1M
公開 測資點#6 (9%): 1.0s , <1M
公開 測資點#7 (9%): 1.0s , <1M
公開 測資點#8 (9%): 1.0s , <1M
公開 測資點#9 (9%): 0.5s , <1M
公開 測資點#10 (10%): 0.5s , <1M
Hint :

在第一個屬性裡,編號3 ~ 7的部隊裡至少選三個。
在第二個屬性裡,編號8 ~ 10的部隊裡至少選三個。
在第三個屬性裡,編號6 ~ 8的部隊裡至少選一個。
在第四個屬性裡,編號1 ~ 3的部隊裡至少選一個。
在第五個屬性裡,編號10 ~ 11的部隊裡至少選一個。
最精簡的部隊是選:3 6 7 8 9 10,只有六種。

Tags:
出處:
彰雲嘉團練 pt 4. [管理者:
qqrainbow (愛蜜莉雅)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」