2011-06-10 20:44:41Morris
d645. 輪下亡魂
http://zerojudge.tw/ShowProblem?problemid=d645
內容 ：
路過的鴨上次在你的幫忙之後，
成功解決鴨子王(duckingod)的難題而復活了！
但是有一天牠過馬路的時候…
牠因為闖紅燈結果被車撞死了囧
(…那有什麼辦法，鴨子又看不懂紅綠燈)
無奈的duckingod決定再給路過的鴨一次機會！
但是這次的題目比上次更難！
同樣是鴨飼料問題，限定的體積要吃得最飽，
但是現在除了普通的鴨飼料(只能吃一次)之外多了另外兩種神奇的飼料！
1.神的鴨飼料！不管被吃幾次都不會消失(吃到飽?)
2.分身鴨飼料！在一定次數內被吃幾次都不會消失
成功解決鴨子王(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次
第一行有兩個正整數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)
(答案保證不超過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
提示
：
共計三個測資點，配分30％、35％、35％
出處
：
/**********************************************************************************/
/* Problem: d645 "輪下亡魂" from jack1 */
/* Language: C */
/* Result: AC (8ms, 272KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-06 09:36:10 */
/**********************************************************************************/
#include<stdio.h>
main() {
int I, C, a, b, c;
while(scanf("%d %d", &I, &C) == 2) {
int v, w, t;
int DP[1001] = {};
while(I--) {
scanf("%d %d %d", &v, &w, &t);
if(t == -1) {
for(a = w; a <= C; a++) {
if(DP[a] < DP[a-w] + v)
DP[a] = DP[a-w] + v;
}
}
else {
while(t) {
for(a = C - w; a >= 0; a--)
if(DP[a+w] < DP[a] + v)
DP[a+w] = DP[a] + v;
t--;
}
}
}
printf("%d\n", DP[C]);
}
return 0;
}
上一篇：d644. 壞脾氣小小皮
下一篇：d646. I2A的陰謀