時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
超市有 n 件商品。每件商品 i 需要恰好一個時間單位才能賣出，售出可得利潤 pᵢ，且必須在截止時間 dᵢ 以前或恰好於 dᵢ 完成。時間從 0 開始，一次只能處理一件商品。 可以只選擇部分商品並安排順序。請求能取得的最大總利潤。
輸入格式
輸入至檔案結尾。每組先給 n，0 ≤ n ≤ 10000；接著 n 對整數 pᵢ dᵢ，1 ≤ pᵢ, dᵢ ≤ 10000。空白與換行可任意出現在數字之間。n = 0 是空商品集合，仍須輸出答案，不是終止標記。
輸出格式
每組資料輸出最大總利潤，各組結果各佔一行。
題目來源：UVa 1316 — Supermarket。 原題：https://onlinejudge.org/external/13/1316.pdf
範例測資
範例輸入 1
4 50 2 10 1 20 2 30 1 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
範例輸出 1
80 185
請先登入後再提交程式碼
討論與題解
載入討論區…