Program QingGongHui;
Var c,w:array[0..500] of longint;
f:array[0..500,0..5000] of longint;
flag:array[1..500] of boolean;
i,j,k,s,m,n,t,sum:longint;
Function Max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
Procedure Dfs(i,j,s:longint);
var k:longint;
begin
if s=f[n,m] then
begin
for k:=1 to n do
if flag[k] then write(k,' ');
halt;
end;
if f[i,j]=f[i-1,j-c[i]]+w[i] then
begin
flag[i]:=true;
Dfs(i-1,j-c[i],s+w[i]);
end
else Dfs(i-1,j,s);
end;
Begin
fillchar(flag,sizeof(flag),0);
readln(n,m);
for i:=1 to n do
begin
readln(j,k,s);
c[i]:=j*s;
w[i]:=k*s;
end;
for i:=1 to n do
for j:=0 to m do
if j>=c[i] then
f[i,j]:=max(f[i-1,j-c[i]]+w[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
writeln(f[n,m]);
Dfs(n,m,0);
End.
program qgh;
var
a:array [0..500,1..5000] of longint;
v,w:array [1..500] of longint;
n,m,s:longint;
i,j,k:longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
procedure find(d,t:longint);
begin
if d=0 then exit;
if a[d-1,t-v[d]]+w[d]=a[d,t] then
begin
find(d-1,t-v[d]);
write(d,' ');
end
else find(d-1,t);
end;
begin
readln(n,m);
for i:=1 to n do
begin
readln(v[i],w[i],s);
v[i]:=v[i]*s;
w[i]:=w[i]*s;
end;
fillchar(a,sizeof(a),0);
for i:=1 to n do
for j:=1 to m do
if (j>=v[i]) then
begin
a[i,j]:=max(a[i-1,j],a[i-1,j-v[i]]+w[i]);
end
else
a[i,j]:=a[i-1,j];
writeln(a[n,m]);
find(n,m);
readln;
end.
状态: Unaccepted
测评机: Xeost[5]
得分: 0分
提交日期: 2011-8-15 21:35:00
有效耗时: 1298毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 测试结果错误.错误结果为:70701
5 18 40 42 45 48 60 79 83 84 90 92 103 105 109 112 120 133 154 171 175 191 196 214 218 225 227 238 241 247 251 259 273 280 293 304
正确结果应为:70701
5 18 42 45 48 60 90 92 105 109 120 133 154 171 175 191 196 214 218 225 227 238 241 259 273 293 304
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 通过本测试点|有效耗时188ms
测试结果5: 通过本测试点|有效耗时172ms
测试结果6: 测试结果错误.错误结果为:137034
13 14 15 17 24 28 34 49 52 56 59 65 77 85 88 97 98 101 102 110 121 126 127 130 140 141 145 150 158 162 173 174 181 182 184 187 202 204 205 208 219 221 226 238 244 245 246 251 253 256 278 285
正确结果应为:137034
13 14 15 17 24 28 34 49 52 56 59 65 77 85 88 97 98 101 102 110 121 126 130 140 141 145 150 158 162 173 174 181 182 184 187 202 204 205 208 219 221 226 244 245 251 253 256 285
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时188ms
测试结果9: 测试结果错误.错误结果为:100892
5 9 19 28 33 34 35 37 45 47 57 72 74 81 86 90 91 100 102 119 120 122 125 127 128 130 137 138 140 144 145 147 148 154 161 162 173 181 186 188 191 203 204 211
正确结果应为:100892
5 9 19 28 33 34 35 37 45 47 57 72 91 100 102 119 120 122 128 130 137 138 140 144 145 147 148 154 161 162 173 181 186 188 191 203 204 211
测试结果10: 通过本测试点|有效耗时234ms