program r329;
type
note=record
value,time,h,w:longint;
end;
var
f:array[0..100,0..100] of longint;
a:array[1..100] of note;
st,en:array[1..100] of longint;
n,m,t,i,j,k,l,best,len:longint;
procedure sort;
var
i,j:integer;
tmp:note;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i].value>a[j].value then begin
tmp:=a[i];a[i]:=a[j];a[j]:=tmp;
end;
end;
begin
read(n,m,t);
for i:=1 to n do
with a[i] do
read(value,time,h,w);
sort;
st[1]:=1;
len:=1;
for i:=2 to n do
if a[i].value<>a[i-1].value then begin
en[len]:=i-1;
inc(len);
st[len]:=i;
end;
en[len]:=n;
for l:=1 to len do
for i:=m downto 0 do
for j:=t downto 1 do begin
for k:=st[l] to en[l] do
with a[k] do
if (i>=time)and(j>h)and(f[i-time][j-h]+w>f[i][j]) then
f[i,j]:=f[i-time][j-h]+w;
if f[i][j]>best then best:=f[i][j];
end;
writeln(best);
end.
但我看了看,有这么点问题。
for i:=m downto 0 do
for j:=t downto 1 do begin
for k:=st[l] to en[l] do
with a[k] do
if (i>=time)and(j>h)and(f[i-time][j-h]+w>f[i][j]) then
f[i,j]:=f[i-time][j-h]+w;
if f[i][j]>best then best:=f[i][j];
end;
i的循环是m downto 0,对应的应是体力,j对应的是时间。而你在循环里面确实i对应体力,j对应时间。注意输入第一行是n,m,t;体力在先,而后面每封信是的输入是时间在先。
第二个问题是,你的体力是downto到1.应该不对,因为这里的状态时表示消耗了多少体力,而非剩余体力。应该是体力-1 downto 0才对。你试试改了交一下,我觉得没问题了。
不是开玩笑,这是真的。这题目前就我过了吧
其实在运行结果上应该是一样的。
lz这样的算法得出的最大值应该等于f[m,t]