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