回『原創/不分類題庫』
d645. 輪下亡魂
標籤 : DP
通過比率 : 307人/328人 ( 94% ) [非即時]
評分方式：
Tolerant

最近更新 : 2010-02-26 17:08

內容
路過的鴨上次在你的幫忙之後，
成功解決鴨子王(duckingod)的難題而復活了！

但是有一天牠過馬路的時候…
牠因為闖紅燈結果被車撞死了囧
(…那有什麼辦法，鴨子又看不懂紅綠燈)

無奈的duckingod決定再給路過的鴨一次機會！
但是這次的題目比上次更難！
同樣是鴨飼料問題，限定的體積要吃得最飽，
但是現在除了普通的鴨飼料(只能吃一次)之外多了另外兩種神奇的飼料！
1.神的鴨飼料！不管被吃幾次都不會消失(吃到飽?)
2.分身鴨飼料！在一定次數內被吃幾次都不會消失
輸入說明
每個測資點僅一組測資。
第一行有兩個正整數i,c代表飼料種類數、鴨子胃的容量，(1<=i<=1000 , 1<=c<=1000)
接下來i行每一行的飼料資料有三個正整數v,w,t，(1<=v<=10000,1<=w<=c,-1<=t<=100)
v是該飼料的飽足感、w是體積、t則代表飼料的類型：
t=-1表示是神的鴨飼料！
t=1表示是普通鴨飼料！
t>1表示是分身鴨飼料，可以被吃t次
輸出說明
請輸出路過的鴨能取得的最大飽足感。
(答案保證不超過1000000000)
範例輸入 #1 
7 100
2 4 -1
1 3 -1
60 10 1
40 10 1
10 10 3
5 6 7
6 5 2
範例輸出 #1 
174
測資資訊：
記憶體限制： 512 MB
公開 測資點#0 (30%): 1.0s , <1K
公開 測資點#1 (35%): 1.0s , <1M
公開 測資點#2 (35%): 1.0s , <1M
提示 ：

 共計三個測資點，配分30％、35％、35％

 

標籤:
DP
出處:
jack1 [管理者： jack1 (我是韜哥我忘了拿通知單) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」