编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 338ms

├ 测试数据 08：答案正确... 306ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：644ms

竟然不是0MS

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

主件附件绑在一起上,呵呵

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

因为附件太少，所以把其转化为标准分组背包，预处理数据即可。

program depend_pack;

const

maxm=60;

maxn=20000;

var

totk,n,m,i,k,v,im:longint;

c,w:array[1..maxm]of longint;

sum,l:array[1..maxm]of integer;

s:array[1..maxm,0..2]of integer;

cost,worth:array[1..maxm,1..4]of longint;

f:array[1..maxn]of longint;

function max(a,b:longint):longint;

begin

if a>b then max:=a

else max:=b;

end;

begin

readln(n,m);

n:=n div 10;

fillchar(s,sizeof(s),0);

fillchar(w,sizeof(w),0);

for i:= 1 to m do

begin

readln(c[i],im,l[i]);

c[i]:=c[i] div 10;

w[i]:=c[i] *im;

if l[i]0 then

begin

inc(s[l[i],0]);

s[l[i],s[l[i],0]]:=i;

end;

end;

totk:=0;

for i:= 1 to m do

if l[i] = 0 then

begin

inc(totk);

case s of

0:begin

sum[totk]:=1;

worth[totk,1]:=w[i];

cost[totk,1]:=c[i];

end;

1:begin

sum[totk]:=2;

worth[totk,1]:=w[i];

worth[totk,2]:=w[i]+w[s];

cost[totk,1]:=c[i];

cost[totk,2]:=c[i]+c[s];

end;

2:begin

sum[totk]:=4;

worth[totk,1]:=w[i];

worth[totk,2]:=w[i]+w[s];

worth[totk,3]:=w[i]+w[s];

worth[totk,4]:=w[i]+w[s]+w[s];

cost[totk,1]:=c[i];

cost[totk,2]:=c[i]+c[s];

cost[totk,3]:=c[i]+c[s];

cost[totk,4]:=c[i]+c[s]+c[s];

end;

end;

end;

fillchar(f,sizeof(f),0);

for k:= 1 to totk do

for v:= n downto 0 do

for i:= 1 to sum[k] do

if v-cost[k,i]>=0 then

f[v]:=max(f[v],f[v-cost[k,i]]+worth[k,i]);

writeln(f[n]*10);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

PS：这道题是提高组的就明显比普及组的拓展性。这里每个主件都可以用0，1，2个附件。

也就是说，我们可以写成这样的转移方程：(用a[i].v数组表示价格，用a[i].w数组表示重要度*价格)。

Opt[j]:=max(opt[j],opt[j-a[i].v[0]]+a[i].w[0]]);

Opt[j]:=max(opt[j],opt[j-a[i].v[0]-a[i].v[1]]+a[i].w[0]+a[i].w[1]);

Opt[j]:=max(opt[j],opt[j-a[i].v[0]-a[i].v[2]]+a[i].w[0]+a[i].w[2]);

Opt[j]:=max(opt[j],opt[j-a[i].v[0]-a[i].v[1]-a[i].v[2]]+a[i].w[0]+a[i].w[1]+a[i].w[2]);

在这里我们可以将价格做个小小的优化由于价格是10元的整倍数，所以我们可以将读进来的价格div10，输出在*10，可以有效地节约空间。（注意处理，由于一开始读进来没处理好，白白浪费10个小时的调试时间- -|||）

我是把它当成01背包做了

应该是04背包

但我刚做的时候 第89组过不去

调试发现是设不了那么大的数组f【m】【n】

后来我发现可以改进f【2】【m】

也就是说所有01背包都可以这么处理啦

请问你们也像我这样处理吗 还是有什么别的对付89组测试数据的高招

http://hi.baidu.com/shenjoy/blog/item/f1ea1f6da995cbfd4316941e.html

这是我的空间 提供参考

Vag 6k

唉！

终于过了！我的AC率！！！！！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 775ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：775ms

第九个点有点慢...

其实核心是类似与0/1背包的问题，只要能做好预处理，便可以AC。

在预处理中根据q[i]是谁的附件便可，因为最多只有2个附件，如果v[q[i]][1]!=0便是第2个附件，则v[q[i]][2]=v[i][0]。做完这个后据需要进行整理，将主件整理到一起。之后按0/1背包问题去做便可！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

分五种情况：

1、只买本身

2、本+附件1

3、本+附2

4、本+附1+附2

5、不买

一开始看错题了,改了之后一次AC

为啥去年考试的时候没对啊？？？

langguixing

太帅了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 666ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：666ms

30行的搜索。。。。。性价比真高。。。

弄错一个变量名,WA了N次

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

AC!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

知道了用状态描述表示第i个主件有无被使用，就可以解决i个附件的问题了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms