時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
每份廣告訂單指定起始樓層 A、占用樓層數 B 及收益 C，會完整占用 A 到 A+B−1 樓。每個樓層只能放一份廣告，不能部分接受或移動廣告。選擇互不重疊的訂單，使總收益最大。
輸入格式
第一行 T（T ≤ 50）。每筆先給 N（1 ≤ N ≤ 30000），再給 N 行 A、B、C，0 ≤ A ≤ 100000，1 ≤ B ≤ 100000，1 ≤ C ≤ 1000。
輸出格式
每筆輸出 Case k: P，k 從 1 開始，P 為最大收益。
題目來源：UVa 11908 — Skyscraper，CPE 歷屆試題。 原題：https://onlinejudge.org/external/119/11908.pdf
範例測資
範例輸入 1
1 3 1 5 1 2 10 3 7 12 1
範例輸出 1
Case 1: 3
請先登入後再提交程式碼
討論與題解
載入討論區…