讨论 / 数据可否一定正确?
zjsxzjb 2008-08-26 06:01:00
点我顶贴 收藏 删除
此题我用DP方法,注意点是多个价值相同的物品要一起处理,给出程序,如有错误,麻烦指正,也麻烦给出正解:

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.

#1 小孩的马甲@2008-08-23 06:22:00
回复 删除
哥们本来想改了提交下试试,结果no compiled,我手头也没pascal,你这程序有问题吗?

但我看了看,有这么点问题。

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才对。你试试改了交一下,我觉得没问题了。

#2 guoshi3@2008-08-23 06:23:00
回复 删除
呵,ls是我马甲,用来交你那题的(这里做过的题就不能交了,不好),分要给给我吧....呵呵

不是开玩笑,这是真的。这题目前就我过了吧

#3 xiaokeke@2008-08-23 16:19:00
回复 删除
第二个问题是,你的体力是downto到1.应该不对,因为这里的状态时表示消耗了多少体力,而非剩余体力。应该是体力-1 downto 0才对。你试试改了交一下,我觉得没问题了。

其实在运行结果上应该是一样的。

lz这样的算法得出的最大值应该等于f[m,t]

#4 guoshi3@2008-08-23 20:56:00
回复 删除
噢对,我说呢,所以一个是>=time一个是>h。明白了,我错了
#5 cc@2008-08-26 05:49:00
回复 删除
这个题应该不用排序的,都一样。
#6 cc@2008-08-26 05:55:00
回复 删除
当然要分组,用一个record记下来,很简单的
#7 tamade@2008-08-26 06:01:00
回复 删除
record?

麻烦了吧

查看更多回复
提交回复