e686: 11908 - Skyscraper
Tags : DP
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-11-13 09:33

Content

Build n’Profit建築公司即將建造其最高的建築物。它將會是世界上最高的建築,並且能容納數十萬人。
不過,任何規模的建築物的建造和維護成本都非常高,即使在出售和出租所有空間之後,也很難滿足成本要求。
幸運的是,他們提出了一個很好的解決方案。他們將在建築物的外牆上放置廣告,並收取巨額費用。這將有助於抵消一些成本並帶來利潤。
但是,來自該廣告空間的潛在購買者的提出了一個新問題:
每個客戶都希望將特定大小的廣告放置在特定的高度。
每個廣告訂單都指定其位置(即廣告的最低樓層)及其大小(即其覆蓋的樓層數,包括起始樓層)。
每個廣告都覆蓋建築物的整個表面,因此,沒有兩個廣告可以佔據同一樓層,也不能部分覆蓋樓層。
每個訂單還包括將廣告放置在建築物上所能賺取的金額。當然,如果僅放置一部分廣告或放置在任何其他位置,則不會賺錢。
由於許多廣告希望與其他廣告使用相同的樓層,因此通常無法選擇所有樓層。
您是否可以幫助選擇接受哪個訂單,從而滿足上述限制並最大程度地獲利?

Input

輸入的第一行包含一個整數T (T ≤ 50),代表測資數量。
每組測資第一行為一個整數N (1 ≤ N ≤ 30000),代表廣告訂單的數量。
接下來N行,每行包含三個整數A (0 ≤ A ≤ 10^5),B (1 ≤ B ≤ 10^5),C (1 ≤ C ≤ 1000)。
A代表最低樓層,B代表廣告覆蓋的樓層數(包括最低樓層),C代表放置該樓層所賺取的金額。

Output

對於每組測資,請輸出可以獲得的最大利潤。

Sample Input
1
3
1 5 1
2 10 3
7 12 1
Sample Output
Case 1: 3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
DP
出處:
UVA [管理者:
ig99lp33lp33 (원스)
]


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