一天，小紫被賦予了一個運送貨物的任務，雇主給了她一輛不管是造型或是功能都很奇異的大貨車。
這輛貨車會先把車後面的一條長條狀的載物臺放下來，每個等間隔距離的位置都裝有一個載物箱，為了防止箱子亂動，每個箱子都被定死了位置。
雇主告訴小紫，由於他所剩時間不多，希望她到了指定地點後把盡量讓載回來的物品價值最大，這樣生意才至少能夠做的不會太慘，另外就是每個物品都有標示重量和價值，所以不用擔心計算上的問題。
小紫很順利地將貨車開到了指定地點，面對這些排列整齊的貨物，小紫很輕鬆地就想到了著名的資訊問題──背包問題。
「這太簡單了！波路特石教過我！」
小紫很開心地就寫完了背包問題的程式，實際拿去操作之後才發現事情大條了！將載物臺捲上去的馬達居然無法運作，還發出了恐怖的聲音。
認為自己計算沒錯的小紫滿腦子疑惑，思索了一陣子才發現問題的關鍵點──力矩！
重物如果放在離馬達越遠的地方，所造成的力矩就會越大，進而使轉動的困難度大大增加，經過精密的計算後，小紫好不容易才計算出了最大承受上限的力矩，可是卻不知道接下來如何進行下去。
現在告訴你力矩承受上限為τ(重量×長度)，每個箱子間隔都是一長度單位，載物臺的長度最多只能放下L個物品，和每個物品的重量和價值，你能夠告訴小紫她能載回去的最大價值嗎？
輸入首行會有三個數字以空格隔開
分別代表物品數量n、力矩承受上限τ、載物臺長度L
接下來n行各有兩個數字wi、vi以空格隔開，代表第i個物品的重量及價值。
1≤L≤n≤200、1≤τ≤1000、1≤wi、vi≤100
輸出在力矩承受上限內載物可得到的最大價值。
5 120 5 20 30 80 60 30 40 30 25 10 20
90
Hint：
以以下順序擺設物品：
20 30 10
(30) (40) (20)
所造成的力矩為20×1+30×2+10×3 = 110
得到的價值為 30+40+20=90
也同時是最大價值的選法
第1~2測資點滿足n≤20
第3測資點滿足對於所有的1≤i,j≤n都有vi=vj
第4~6測資點滿足n=L
第7~10測資點無特別限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||