d645: 輪下亡魂
標籤 : DP
通過比率 : 94% (201 人 / 213 人 ) (非即時)
評分方式:
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)
範例輸入
7 100
2 4 -1
1 3 -1
60 10 1
40 10 1
10 10 3
5 6 7
6 5 2
範例輸出
174
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (30%): 1.0s , <1K
公開 測資點#1 (35%): 1.0s , <1M
公開 測資點#2 (35%): 1.0s , <1M
提示 :

 共計三個測資點,配分30%、35%、35%

 

標籤:
DP
出處:
jack1 [編輯:
jack1 (我是韜哥我忘了拿通知單)
]


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