SSL 2295暗黒破壊神(dp)
1994 ワード
暗黒破壊神
Description
退屈中のxちゃんはDiablo Iを游びました...ゲームの主人公にはn個の魔法があり、各魔法はいくつかのレベルに分けられている.i番目の魔法はp[i]のレベル(0を除く)がある.各魔法のレベルごとに1つの効果値がある.1つのj級のi種の魔法の効果値はw[i][j]魔法のレベル1に上がるには、相応の魔法書を購入するために金貨が必要である.第i个魔法的魔法书价格为c[i]而小x只有m个金币(好孩子不用修正器)あなたの任务は小xが魔法书をどのように买ってすべての魔法の効果値の和を最大にすることができるかを决めるのを助けることです.
Input
1行目をスペースで区切った2つの整数n(0以下n行記述n個の魔法i+1行記述i個目の魔法フォーマットは以下の通り(0 c[i]p[i]w[i][1]w[i][2]...w[i][p[i]]
Output
最初の行は整数を出力します.つまり、最大効果です.
Sample Input
Sample Output
Hint
0< n< =100,0< m <=500,0 < p[i] <= 50,0 < c[i] <=10
分析:簡単なリュックサックで、肝心なのは経路を記録することで、b[i,j]が最大効果を示すときにi冊目の魔法書にj元の等級を費やし、最後に再帰的に出力すればいい.
f[i,j]=max(f[i,j],f[i-1,j-k*c[i]]+w[i,k],(1
コード#コード#
const maxn=500; var f,a,b:array[0..maxn,0..maxn] of longint; c,p:array[0..maxn] of longint; i,j,k,n,m,maxf,x,y:longint; procedure print(x,y:longint); begin if x=0 then exit; print(x-1,y-b[x,y]*c[x]); writeln(b[x,y]); end; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin readln(n,m); for i:=1 to n do begin read(c[i],p[i]); for j:=1 to p[i] do read(a[i,j]); readln; end; for i:=1 to n do for j:=1 to m do begin f[i,j]:=f[i-1,j]; for k:=0 to p[i] do begin if k*c[i]>j then break; if f[i,j] begin f[i,j]:=f[i-1,j-k*c[i]]+a[i,k]; b[i,j]:=k; end; end; end; writeln(f[n,m]); for j:=m downto 1 do for i:=n downto 1 do if f[i,j]>=maxf then begin maxf:=f[i,j]; x:=i; y:=j; end; print(x,y); for i:=x+1 to n do writeln(0); end.
Description
退屈中のxちゃんはDiablo Iを游びました...ゲームの主人公にはn個の魔法があり、各魔法はいくつかのレベルに分けられている.i番目の魔法はp[i]のレベル(0を除く)がある.各魔法のレベルごとに1つの効果値がある.1つのj級のi種の魔法の効果値はw[i][j]魔法のレベル1に上がるには、相応の魔法書を購入するために金貨が必要である.第i个魔法的魔法书价格为c[i]而小x只有m个金币(好孩子不用修正器)あなたの任务は小xが魔法书をどのように买ってすべての魔法の効果値の和を最大にすることができるかを决めるのを助けることです.
Input
1行目をスペースで区切った2つの整数n(0以下n行記述n個の魔法i+1行記述i個目の魔法フォーマットは以下の通り(0 c[i]p[i]w[i][1]w[i][2]...w[i][p[i]]
Output
最初の行は整数を出力します.つまり、最大効果です.
Sample Input
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10Sample Output
11
1
0
3Hint
0< n< =100,0< m <=500,0 < p[i] <= 50,0 < c[i] <=10
分析:簡単なリュックサックで、肝心なのは経路を記録することで、b[i,j]が最大効果を示すときにi冊目の魔法書にj元の等級を費やし、最後に再帰的に出力すればいい.
f[i,j]=max(f[i,j],f[i-1,j-k*c[i]]+w[i,k],(1
コード#コード#
const maxn=500; var f,a,b:array[0..maxn,0..maxn] of longint; c,p:array[0..maxn] of longint; i,j,k,n,m,maxf,x,y:longint; procedure print(x,y:longint); begin if x=0 then exit; print(x-1,y-b[x,y]*c[x]); writeln(b[x,y]); end; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin readln(n,m); for i:=1 to n do begin read(c[i],p[i]); for j:=1 to p[i] do read(a[i,j]); readln; end; for i:=1 to n do for j:=1 to m do begin f[i,j]:=f[i-1,j]; for k:=0 to p[i] do begin if k*c[i]>j then break; if f[i,j] begin f[i,j]:=f[i-1,j-k*c[i]]+a[i,k]; b[i,j]:=k; end; end; end; writeln(f[n,m]); for j:=m downto 1 do for i:=n downto 1 do if f[i,j]>=maxf then begin maxf:=f[i,j]; x:=i; y:=j; end; print(x,y); for i:=x+1 to n do writeln(0); end.