讨论 - 评测机出问题了吗？

shushi0113 2008-08-15 18:10:00

点我顶贴收藏删除

这道题目明明是01背包问题，和采药一样，就是数据有差别，但是为什么AC不了··

#1 vinence@2008-07-24 08:27:00

回复删除

数据规模大了.

#2 vinence@2008-07-24 08:27:00

回复删除

数据规模大了.

#3 binarie@2008-07-24 17:05:00

回复删除

O(vn) = 10000^2 = 100000000

tle...

#4 shushi0113@2008-07-24 18:07:00

回复删除

怎么我的输出全是0····但是FPC没有错误

#5 renqing@2008-07-24 19:14:00

回复删除

公告 Announcement : 恢复测评(PID172-207暂时不测评,请勿提交)……；RQNOJ一周年邀请赛通知

#6 shuizilong96@2008-08-14 01:43:00

回复删除

const max=10000；

var n,m,i,j:longint；

a,b:array [1..max] of integer；

c:array [0..max] of longint；

begin

readln(m,n)；

for i:=1 to n do

readln(a[i],b[i])；

for i:=1 to n do

for j:=m downto a[i] do

if c[j-a[i]]+b[i]>c[j] then c[j]:=c[j-a[i]]+b[i]；

write(c[m])；

end.

数组不够大

#7 binarie@2008-08-14 02:45:00

回复删除

可以试试用单调队列优化下。。

#8 Jollwish@2008-08-14 06:21:00

回复删除

var p:array[1..10000]of longint；

i,j,a,b,n,m:longint；

begin

readln(n,m)；

for i:=1 to m do

begin

readln(a,b)；

for j:=n downto a do if p[j-a]+b>p[j] then p[j]:=p[j-a]+b；

end；

write(p[n])；

end.

#9 renqing@2008-08-15 18:10:00

回复删除

这道题目要用DP的说