sxpeter 2008-06-08 05:49:00
点我顶贴
收藏
删除
RT
大牛门帮忙看看
(AC)http://www.rqnoj.cn/Status_Show.asp?SID=3610
(WA)http://www.rqnoj.cn/Status_Show.asp?SID=52508
附代码
var
t,m,i,j:longint;
a,b:array[1..1000]of longint;
f:array[0..1000]of longint;
begin
read(t,m);
for i:=1 to m do read(a[i],b[i]);
f[0]:=1;
for i:=1 to m do
for j:=t-a[i] downto 0 do
if (f[j]>0)and(f[j]+b[i]>f[j+a[i]]) then
begin
if j=0 then f[j+a[i]]:=f[j]+b[i]-1
else f[j+a[i]]:=f[j]+b[i];
end;
for i:=0 to t do
if f[i]>m then m:=f[i];
writeln(m);
end.
这两题明显是很经典的DP。。。哎
#1 fjxmlhx@2008-06-08 05:49:00
1815
回复
删除
var
n,m,i,j,a,b:longint;
f:array[0..15000] of longint;
begin
readln(n,m);
for i:=1 to m do
begin
readln(a,b);
for j:=n downto a do if f[j-a]+b>f[j] then f[j]:=f[j-a]+b;
end;
writeln(f[n]);
end.