点这里查看
讨论 / 求此题解法
noip2012 2011-03-27 06:35:00
点我顶贴 收藏 删除
是否要用到单调队列？
#1 sunzhouyi@2011-03-26 01:56:00
回复 删除
~~

单调队列能优化到O(VN)，显然还是过不去~~

#2 noip2012@2011-03-26 02:00:00
回复 删除
那应该是10000*10000吧，我觉得差不多

除了这个还有什么方法？

#3 sunzhouyi@2011-03-26 02:09:00
回复 删除
回复 板凳noip2012 的帖子

RQ的破评测机10000*10000估计P就挂了

其他的方法不太清楚，想想~~

#4 sunzhouyi@2011-03-26 02:22:00
回复 删除
~~~~~~~~

我们显然傻叉了

这完全背包不用优化就是O(VN)的啊

像这样就过了囧……

var f,p,t:array[0..10000] of longint;

m,n,i,j:longint;

begin

readln(m,n);

for i:=1 to n do readln(p[i],t[i]);

for i:=1 to n do

for j:=t[i] to m do

if f[j-t[i]]+p[i]>f[j] then f[j]:=f[j-t[i]]+p[i];

writeln(f[m]);

end.

#5 luoxiangyu@2011-03-26 03:55:00
回复 删除
LZ和GYZ一个学校！！
#6 sunzhouyi@2011-03-26 04:19:00
回复 删除
回复 地下室luoxiangyu 的帖子

刚发现！

ORZ！！！

#7 noip2012@2011-03-26 06:37:00
回复 删除
回复 地板sunzhouyi 的帖子

orz

#8 noip2012@2011-03-26 06:39:00
回复 删除
回复 地下室luoxiangyu 的帖子

我和GYZ现在不是一个学校，但他以前是在这个学校就读的，这个学校只有初一到初三，而他现在已经高一了

#9 noip2012@2011-03-26 06:50:00
回复 删除
回复 地板sunzhouyi 的帖子

您是神叉，我才是傻叉

#10 sunzhouyi@2011-03-27 06:35:00
回复 删除
回复 地核noip2012 的帖子

呃

我作为一个傻叉胡乱被ORZ显然是要掉RP的

ORZ ORZ ORZ

补回来…………

查看更多回复
提交回复