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.