捆绑法好理解适用范围也广。

program P1313;
var Left,Right,v,p:array[1..60] of longint;
f:array[0..32000] of longint;
Cu:array[1..60] of boolean;
i,j,N,m,q:longint;

function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;

begin
fillchar(Left,sizeof(Left),0);
fillchar(Right,sizeof(Right),0);

readln(N,m);
for i:=1 to m do begin
readln(v[i],p[i],q);
Cu[i]:=(q=0);
if q<>0 then
if Left[q]=0 then Left[q]:=i else Right[q]:=i;
end;

fillchar(f,sizeof(f),0);
for i:=1 to m do
if Cu[i] then
for j:=N downto v[i] do begin
f[j]:=max(f[j],f[j-v[i]]+v[i]*p[i]);
if Left[i]<>0 then
if j-v[i]-v[Left[i]]>=0 then f[j]:=max(f[j],f[j-v[i]-v[Left[i]]]+v[i]*p[i]+v[Left[i]]*p[Left[i]]);

if Right[i]<>0 then
if j-v[i]-v[Right[i]]>=0 then f[j]:=max(f[j],f[j-v[i]-v[Right[i]]]+v[i]*p[i]+v[Right[i]]*p[Right[i]]);

if (Left[i]<>0) and (Right[i]<>0) then
if j-v[i]-v[Left[i]]-v[Right[i]]>=0 then
f[j]:=max(f[j],f[j-v[i]-v[Left[i]]-v[Right[i]]]+v[i]*p[i]+v[Left[i]]*p[Left[i]]+v[Right[i]]*p[Right[i]]);
end;

writeln(f[N]);
end.

分组，两个三次循环 OK

这是一个典型的有依赖的背包，实际上也就是一个加了点小小限制的分组背包；

首先，我们先对物品进行分组；用v[i]记录i的价钱（也就是重量），w[i]记录i的价值,c记录i的附件个数，c表示i的第j个附件的编号，c=-1代表这是附件；

read(n,m);

n:=n div 10;

fillchar(c,sizeof(c),0);

for i:=1 to m do

begin

read(v[i],w[i],q);

w[i]:=v[i]*w[i];

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

if q0 then

begin

inc(c[q,0]);

c[q,c[q,0]]:=i;

c:=-1;

end;

end;

然后是动归模块：

我们用num[k,j]表示总花费为j时，得到最大价值f[j]是否用到k组的主件；则枚举每一组的副件i时，就有

f[j]:= max {f[j-v[k]-v[c[k,i]]]+w[k]+wc[k,i],

f[j-v[c[k,i]]]+wc[k,i]}

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

fillchar(num,sizeof(num),0);

for k:=1 to m do

if c[k,0]>=0 then

begin

for j:=n downto v[k] do

begin

if f[j]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

见之有依赖的背包问题

由于用了STL,速度太慢

仍然是背包问题。。。

#include

#include

int n,m;

int cost[61],v[61],q[61],son[61][2],sonn[61];

int f[32001];

int max(int a,int b){return a>b?a:b;}

int main()

{

memset(cost,0,sizeof(cost));

memset(v,0,sizeof(v));

memset(q,0,sizeof(q));

memset(son,-1,sizeof(son));

memset(sonn,0,sizeof(sonn));

memset(f,0,sizeof(f));

scanf("%d%d",&n,&m);

for(int i=1;i0 && j - cost[ son[i][0] ] >= 0 )

tmp = max(tmp,f[j-cost[ son[i][0] ]] + v[ son[i][0] ]);

if(sonn[i]>1 && j - cost[ son[i][1] ] >= 0 )

tmp = max(tmp,f[j-cost[ son[i][1] ]] + v[ son[i][1] ]);

if(sonn[i]>1 && j - cost[ son[i][0] ] - cost[ son[i][1] ] + cost[i] >= 0 )

tmp = max(tmp,f[j-cost[ son[i][0] ]-cost[ son[i][1] ] + cost[i]] + v[ son[i][0] ] + v[ son[i][1] ] - v[i]);

f[j] = tmp;

}

printf("%d\n",f[n]);

}

二维的交了几次都WA掉..直接改成一维的一次AC..郁闷..

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

简单的分组背包，程序的主体是预处理

var

n,m,i,j,k,c,t,s:longint;

f:array[0..32000] of longint;

a,b,num:array[0..60] of longint;

v,w,d:array[0..60,0..4] of longint;

begin

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

fillchar(num,sizeof(num),0);

fillchar(d,sizeof(d),0);

for i:=0 to 60 do d:=-1;

a[0]:=0;b[0]:=0;

readln(n,m);

for i:=1 to m do

begin

readln(a[i],b[i],c);

b[i]:=a[i]*b[i];

if c0 then

begin

inc(num[c]);

d[c,num[c]]:=i;

end

else

d:=0;

end;

t:=0;

for i:=1 to m do

if d=0 then

begin

inc(t);

v[t][1]:=a[i];w[t][1]:=b[i];

v[t][2]:=a[i]+a[d]; w[t][2]:=b[i]+b[d];

v[t][3]:=a[i]+a[d]; w[t][3]:=b[i]+b[d];

v[t][4]:=a[i]+a[d]+a[d]; w[t][4]:=b[i]+b[d]+b[d];

end;

for i:=1 to t do

for j:=n downto 1 do

begin

for k:=1 to 4 do

if (v

不幸啊，等号输成了不等，没编译直接交，只过了两点。。。。。

改后，AC了。。。。

我的通过率。。。。

主副捆绑，很容易解决

var

f:array[0..61,-20000..20000]of longint;

n,m,k,i,j,v1,w1,q,z:longint;

h:array[0..61]of longint;

v,w:array[0..61,0..2]of longint;

function max(a,b,c,d,e:longint):longint;

begin

if a>b then max:=a

else max:=b;

if c>max then max:=c;

if d>max then max:=d;

if e>max then max:=e;

end;

begin

readln(n,m);

k:=0;

for i:=1 to m do

begin

readln(v1,w1,q);

v1:=v1 div 10;

if q=0 then begin inc(k);v[k,0]:=v1;w[k,0]:=w1;h[i]:=k end

else

begin

z:=h[q];

for j:=1 to 2 do

if v[z,j]=0 then

begin

v[z,j]:=v1;

w[z,j]:=w1;

break;

end;

end;

end;

for i:=0 to 61 do

for j:=-20000 to -1 do

f:=-10000;

f[0,0]:=0;

n:=n div 10;

for i:=1 to k do

for j:=1 to n do

f:=max(f,f[i-1,j-v]+v*w,

f[i-1,j-v-v]+v*w+v*w,

f[i-1,j-v-v]+v*w+v*w,

f[i-1,j-v-v-v]+v*w+v*w+v*w);

writeln(f[k,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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

昨天脑子小了，囧，今天1下就A了

这弱智题目都交了两遍

我以后没脸活着见人了，还是去跳楼吧。。。

但是想了好久，想到vijos上还有好多水题给我刷，所以还是放弃死的念头了。

如果有吃错了毒药的，可以看看我的丑程序来洗胃——保证你把吃的什么都吐光。

program p1313;

var

m,n,i,j,k,l,a,b,cc,p:longint;

f:array[0..32000] of longint;

w,c:array[1..60,0..3] of longint;

t,r:array[1..60] of longint;

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

begin

if a>b then exit(a);

exit(b);

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(a,b,cc);

if cc=0 then

begin

inc(p);

r[i]:=p;

w[p,0]:=a;

c[p,0]:=a*b;

end else

begin

inc(t[r[cc]]);

if t[r[cc]]=1 then

begin

w[r[cc],1]:=w[r[cc],0]+a;

c[r[cc],1]:=c[r[cc],0]+a*b;

end;

if t[r[cc]]=2 then

begin

w[r[cc],2]:=w[r[cc],0]+a;

c[r[cc],2]:=c[r[cc],0]+a*b;

w[r[cc],3]:=w[r[cc],1]+a;

c[r[cc],3]:=c[r[cc],1]+a*b;

end;

end;

end;

for i:=1 to p do

for j:=n downto w do

begin

f[j]:=max(f[j],f[j-w]+c);

if (w0) and (j>=w) then

f[j]:=max(f[j],f[j-w]+c);

if w0 then

begin

if (j>=w) then

f[j]:=max(f[j],f[j-w]+c);

if (j>=w)then

f[j]:=max(f[j],f[j-w]+c);

end;

end;

writeln(f[n]);

end.

for j:=1 to m do

for i:=1 to t do

begin

if j>=p

then f:=max(f,f[i-1,j-p]+v) else f:=f;{else f:=f;这句相当重要。}

if (p0)and(j>=p+p)

then f:=max(f,f[i-1,j-p-p]+v+v);

if (p0)and(j>=p+p)

then f:=max(f,f[i-1,j-p-p]+v+v);

if (p0)and(j>=p+p+p)

then f:=max(f,f[i-1,j-p-p-p]+v+v+v);

end;

那个...啥..

弱弱的问下.

为啥我直接dp判断附件的主件是否已经买下来

这样就不能ac捏.

急需大牛求解

附程序：

var

a:array[0..100,0..5000]of longint;

f:array[0..100]of boolean;

b:array[0..100,1..3]of longint;

i,n,m,j,k,l,max:longint;

procedure work(q,w:longint);

begin

if ql then

begin

if (w+b[q+1,1]

我沙茶了、DP判断分析的还不够仔细、、

今天的模拟题也就因为漏了一个判断全WA了、

教训啊、、

type arr=record

l:longint;

r:longint;

end;

var c:array[0..60] of arr;a:array[0..60,0..60] of longint;q,v,n,xx,yy,zz,ii:longint;

w,p:array[0..60] of longint;

f:array[-1..60,0..32000] of longint;

procedure search(x,y:longint);

var max,k:longint;

begin

if y-1 then

if f[c[x].l,k]=-1 then

search(c[x].l,k);

if c[x].r>-1 then

if f[c[x].r,y-p[x]-k]=-1 then

search(c[x].r,y-p[x]-k);

if f[c[x].l,k]+f[c[x].r,y-p[x]-k]>max then

max:=f[c[x].l,k]+f[c[x].r,y-p[x]-k];

end;

max:=max+w[x]*p[x];

if c[x].r-1 then

if f[c[x].r,y]=-1 then

search(c[x].r,y);

if f[c[x].r,y]>max then

max:=f[c[x].r,y];

f[x,y]:=max;

end;

procedure play(x:longint);

var r:longint;

begin

if a[x,0]=0 then exit;

c[x].l:=a[x,1];

for r:=2 to a[x,0] do

c[a[x,r-1]].r:=a[x,r];

end;

begin

assign(input,'budget4.in');reset(input);

assign(output,'p1313.out');rewrite(output);

read(v,n);

for ii:=1 to n do

begin

read(xx,yy,zz);

a[zz,0]:=a[zz,0]+1;

a[zz,a[zz,0]]:=ii;

p[ii]:=xx;

w[ii]:=yy;

end;

for ii:=0 to 60 do

for q:=0 to 32000 do

f[ii,q]:=-1;

for ii:=0 to 60 do

begin

c[ii].l:=-1;

c[ii].r:=-1;

end;

for ii:=0 to n do

play(ii);

search(a[0,1],v);

write(f[a[0,1],v]);

close(input);

close(output);

end.

我强大的使用的树型DP 过一半!!和裸搜一样一样的

呃，C的程序实在太少了。。。

发个补充下吧。。

就是个依赖型的背包~~

#include

struct

{

int cost;

int right;

}save[61][5],step[61][5];

int form[32001];

int n,m;

int main()

{

scanf("%d %d",&n,&m);

int i,j,k,cost,right,tag,top=0;

n/=10;

for(i=1;i=1;j--)

if(tag==save[j][0].right)

{

save[j][0].cost++;

save[j][save[j][0].cost].cost=cost/10;

save[j][save[j][0].cost].right=right;

break;

}

}

}

for(i=1;i1)

{

step[i][0].cost=2;

step[i][2].cost=save[i][1].cost+save[i][2].cost;

step[i][2].right=step[i][1].right+save[i][2].cost*save[i][2].right*10;

}

if(save[i][0].cost>2)

{

step[i][0].cost=4;

step[i][3].cost=save[i][1].cost+save[i][3].cost;

step[i][3].right=step[i][1].right+save[i][3].cost*save[i][3].right*10;

step[i][4].cost=step[i][2].cost+save[i][3].cost;

step[i][4].right=step[i][2].right+save[i][3].cost*save[i][3].right*10;

}

}

for(i=1;i=step[i][1].cost;j--)

{

for(k=1;k=step[i][k].cost) form[j]=(form[j]>form[j-step[i][k].cost]+step[i][k].right)?form[j]:form[j-step[i][k].cost]+step[i][k].right;

}

}

printf("%d\n",form[n]);

return 0;

}

瞧这猥琐的01背包。。

var

max1,n,m,i,j,x:longint;

f:array[1..60] of boolean;

v,p:array[0..60] of longint;

b:array[1..60,0..2] of longint;

a:array[0..32000] of longint;

function max(j,k:longint):longint;

begin

if j>k then exit(j)

else exit(k);

end;

begin

readln(n,m);

fillchar(f,sizeof(f),true);

for i:=1 to m do

begin

read(v[i],p[i]);

read(x);

if x0 then begin b[x,0]:=b[x,0]+1;b[x,b[x,0]]:=i;f[i]:=false; end;

readln;

end;

fillchar(a,sizeof(a),0);

for i:=1 to m do

if f[i] then

begin

for j:=n downto v[i] do

begin

a[j]:=max(a[j-v[i]]+v[i]*p[i],a[j]);

if (b>=1) and (j-v[i]-v[b]>=0) then a[j]:=max(a[j-v[i]-v[b]]+v[i]*p[i]+v[b]*p[b],a[j]);

if (b=2) and (j-v[i]-v[b]>=0) then a[j]:=max(a[j-v[i]-v[b]]+v[i]*p[i]+v[b]*p[b],a[j]);

if (b=2) and (j-v[i]-v[b]-v[b]>=0) then a[j]:=max(a[j-v[i]-v[b]-v[b]]+v[i]*p[i]+v[b]*p[b]+v[b]*p[b],a[j]);

end;

end;

max1:=0;

for i:=0 to n do

if a[i]>max1 then max1:=a[i];

write(max1);

end.

10min不到,秒杀.

终于100A了......没想到我的第100A竟然是这题......