编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

呀呀 虽然我的程序可能不太优

毕竟也是秒杀的程序

还是出来晒晒啊O(∩_∩)O哈！

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

思想吗....

这道题关键在于附件

譬如物品i 有附件x1,x2

那么 物品i可以有4种表现方式

1.单独的物品i 2.物品i+附件x1

3.物品i+附件x2 4.物品i+附件x1+附件x2

f[num,j]代表前num件物品 在有j这么多钱的时候 所得的最大值

那么在处理f[num,j]的时候 可以把1,2,3,4种情况都当做当前物品num来各自DP一遍

所以这样就可以了.....(ˇ——ˇ）

因为第num件物品可取可不取

所以 f[num,j]:=max{f[num-1,j]，f[num-1,j-p[num,k]]+w[num,k]}

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

program p1313;

var i,j,m,n,z,num:longint;

code,count:array[0..70] of longint;

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

f:array[0..70,0..3200] of longint;

begin

readln(n,m); n:=n div 10;

for i:=1 to m do

begin

readln(p,w,code[i]);

p:=p div 10;

z:=code[i];

w:=p*w;

if z>0 then

begin

inc(count[z]);

p[z,count[z]]:=p[z,0]+p;

w[z,count[z]]:=w[z,0]+w;

if count[z]=2 then

begin

inc(count[z]);

p[z,count[z]]:=p[z,1]+p;

w[z,count[z]]:=w[z,1]+w;

end;

end;

end;

num:=0;

for i:=1 to m do

if code[i]=0 then

begin

inc(num);

for z:=0 to count[i] do

for j:=1 to n do

begin

if f[num,j]=p then

if f[num,j]

program xxx;

type

nn=record

wei,val:longint;

end;

var

f,w,c,r:array[0..3200]of longint;

maxw,maxn,i,j,k,x,maxval:longint;

p:array[1..4]of nn;

s:string;

begin

readLn(maxw,maxn);

maxw:=maxw div 10;

for i:=1 to maxn do

begin

readln(w[i],c[i],r[i]);

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

end;

for i:=1 to maxn do

for j:=maxw downto w[i] do

if r[i]=0 then

begin

s:='';

for k:=1 to maxn do

if r[k]=i then s:=s+chr(k+48);

p[1].wei:=w[i];p[1].val:=w[i]*c[i];

k:=1;

if length(s)>=1 then

begin

p[2].wei:=w[i]+w[ord(s[1])-48];

p[2].val:=w[i]*c[i]+w[ord(s[1])-48]*c[ord(s[1])-48];

k:=2;

end;

if length(s)=2 then

begin

p[3].wei:=w[i]+w[ord(s[2])-48];p[3].val:=w[i]*c[i]+w[ord(s[2])-48]*c[ord(s[2])-48];

p[4].wei:=w[i]+w[ord(s[1])-48]+w[ord(s[2])-48];

p[4].val:=w[i]*c[i]+w[ord(s[1])-48]*c[ord(s[1])-48]+w[ord(s[2])-48]*c[ord(s[2])-48];

k:=4;

end;

for x:=1 to k do

if (j-p[x].wei>=0) and (f[j-p[x].wei]+p[x].val>f[j])

then f[j]:=f[j-p[x].wei]+p[x].val;

end;

writeln(f[maxw]*10);

end.

可以绑起来嘛.. 我就是分4类绑起来然后背包..

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

i,j,sk,k,l,m,o,p,n,s,ss,ll,lll:longint;

v,w,q,f:array [0..80000] of longint;

begin

readln(n,m);

for i:=1 to m do

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

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

fillchar(b,sizeof(b),0);

for i:=1 to m do

if q[i]=0 then begin

inc(l);

a:=v[i];

a:=v[i];

a:=v[i];

a:=v[i];

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

b:=b;

b:=b;

b:=b;

end;

for i:=1 to m do

if q[i]0 then begin

inc(a[q[i],0]);

a[q[i],a[q[i],0]+1]:=a[q[i],1]+v[i];

b[q[i],a[q[i],0]+1]:=b[q[i],1]+v[i]*w[i];

end;

for i:=1 to m do begin

a:=a+a-a;

b:=b+b-b;

end;

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

sk:=0;

for i:=1 to m do begin

sk:=sk+a;

for j:=sk downto 1 do

for k:=1 to 4 do

if (j>=a)and(f[j-a]+b>f[j])

then f[j]:=f[j-a]+b; end;

for i:=1 to n do begin

if f[i]>f[0] then f[0]:=f[i];

end;

writeln(f[0]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

本人笨笨地照搬背包P06

不过被我弄得有些复杂了，程序如下：

var i,j,k,knum,n,m:longint;

v,w,q,s,num:array[1..60]of longint;

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

a:array[1..60,1..32000*60,1..2]of longint;

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

begin

readln(n,m);

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

for i:=1 to m do

begin

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

if q[i]>0 then

begin

inc(s[q[i]]);t[q[i],s[q[i]]]:=i;

end;

end;

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

knum:=0;

for i:=1 to m do

if q[i]=0 then

begin

if s[i]=0 then begin

inc(knum);inc(num[knum]);

a[knum,num[knum],1]:=v[i];

a[knum,num[knum],2]:=v[i]*w[i];

end

else

begin

for j:=0 to n do f[j]:=-maxlongint;

f[0]:=0;

for j:=1 to s[i] do

for k:=n-v[i] downto v[t] do

if f[k-v[t]]+v[t]*w[t]>f[k] then

f[k]:=f[k-v[t]]+v[t]*w[t];

for j:=n downto v[i] do

f[j]:=f[j-v[i]]+v[i]*w[i];

inc(knum);

for j:=v[i] to n do

if f[j]>0 then begin

inc(num[knum]);

a[knum,num[knum],1]:=j;

a[knum,num[knum],2]:=f[j];

end;

end;

end;

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

for k:=1 to knum do

for j:=n downto 0 do

for i:=1 to num[k] do

if j-a[k,i,1]>=0 then

if f[j]

简单题，但要细

心

var n,m,g,h,t1,t2,t3:longint;

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

a:array[1..60] of record

zt,zj,ot,oj,tt,tj:longint;

end;

begin

read(n,m);

while gm do begin

g:=g+1;

read(t1,t2,t3);

if t3=0 then begin

a[g].zt:=t1;

a[g].zj:=t1*t2;

end else

if a[t3].oj=0 then begin

a[t3].ot:=t1;

a[t3].oj:=t1*t2

end else begin

a[t3].tt:=t1;

a[t3].tj:=t1*t2;

end;

end;

for g:=1 to m do begin

if a[g].zj0 then

for h:=n downto 1 do begin

if h-a[g].zt>0 then

if f[h-a[g].zt]+a[g].zj>f[h] then f[h]:=f[h-a[g].zt]+a[g].zj;

if (a[g].oj0) and (h-a[g].zt-a[g].ot>0) then

if f[h-a[g].zt-a[g].ot]+a[g].zj+a[g].oj>f[h] then f[h]:=f[h-a[g].zt-a[g].ot]+a[g].zj+a[g].oj;

if (a[g].tj0) and (h-a[g].zt-a[g].tt>0) then

if f[h-a[g].zt-a[g].tt]+a[g].zj+a[g].tj>f[h] then f[h]:=f[h-a[g].zt-a[g].tt]+a[g].zj+a[g].tj;

if (a[g].oj0) and (a[g].tj0) and (h-a[g].zt-a[g].tt-a[g].ot>0) then

if f[h-a[g].zt-a[g].tt-a[g].ot]+a[g].zj+a[g].tj+a[g].oj>f[h] then f[h]:=f[h-a[g].zt-a[g].tt-a[g].ot]+a[g].zj+a[g].tj+a[g].oj;

end;

end;

write(f[n]);

end.

囧死，交了2次，原来把f[g,0]给忘了……

for i:=1 to szj do

for j:=n downto 0 do

case zjof

0:if zj

不除10只有60

除10后AC

编译通过...

├ 测试数据 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

哈哈哈哈哈~

打错个变量，20分.....

某某某，雷人认为将数据都 DIV 10 来优化

const

　　maxn = 60; maxm = 3200;

var

　　i, j, k, n, m, ans : longint;

　　f : array[0..maxn, 0..maxm] of longint;

　　w, fa : array[1..maxn] of longint;

　　val, v : array[1..maxn, 0..4] of longint;

procedure prepare;

var

　　i, j : longint;

begin

　　for i:= 1 to n do

　　if fa[i] = 0 then val[i, 1]:= v[i, 1] * w[i]

　　else

　　if val[fa[i], 2] = 0 then

　　begin

　　　　val[fa[i], 2]:= val[fa[i], 1] + v[i, 1] * w[i];

　　　　v[fa[i], 2]:= v[fa[i], 1] +v[i, 1];

　　end else

　　begin

　　　　val[fa[i], 3]:= val[fa[i], 1] + v[i, 1] * w[i];

　　　　val[fa[i], 4]:= val[fa[i], 2] + val[fa[i], 3] - v[fa[i], 1] * w[fa[i]];

　　　　v[fa[i], 3]:= v[fa[i], 1] + v[i, 1];

　　　　v[fa[i], 4]:= v[fa[i], 2] + v[fa[i], 3] - v[fa[i], 1];

　　end; i:= 1;

　　repeat

　　　　if fa[i] > 0 then

　　　　begin

　　　　　　for j:= i + 1 to n do

　　　　　　begin

　　　　　　　　v[j - 1]:= v[j];val[j - 1]:= val[j];fa[j - 1]:= fa[j];

　　　　　　end;

　　　　　　fillchar(v[n], sizeof(v[n]), 0);

　　　　　　fillchar(val[n], sizeof(val[n]), 0); fa[n]:= 0;

　　　　　　n:= n - 1;

　　　　end else i:= i + 1;

　　until i > n;

end;

{ = = = = = = main = = = = = = }

begin

　　for i:= 1 to n do begin

　　　　readln(v[i, 1], w[i], fa[i]);

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

　　end;

　　prepare;

　　for i:= 1 to n do

　　　　for j:= 1 to m do

　　　　　　for k:= 0 to 4 do

　　　　　　if ((k = 0) or (val[i, k] > 0)) and (j >= v[i, k]) then

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

　　writeln(f[n,m]*10);

end.

const

nmax=60;

mmax=32000;

type

int=longint;

var

dp:array[0..mmax] of int;

C,V,P:array[1..nmax] of int;

f1,f2:array[1..nmax] of int;

i,j:int; n,m:int;

procedure Updata(Cost,Value:int);

begin

if cost>j then exit;

if dp[j-cost]+value>dp[j] then dp[j]:=dp[j-cost]+value;

end;

begin

readln(m,n);

for i:=1 to n do

begin

readln(A[i],C[i],P[i]);

C[i]:=C[i]*A[i];

if P[i]=0 then continue;

if f1[t[i]]=0 then f1[t[i]]:=i

else f2[t[i]]:=i;

end;

for i:=1 to n do

begin

if t[i]0 then continue;

for j:=m downto c[i] do

begin

updata(c[i],v[i]);//主件

if f1[i]0 then

updata(c[i]+c[f1[i]],v[i]+v[f1[i]]);//主件+附件1

if f2[i]0 then

begin

updata(c[i]+c[f2[i]],v[i]+v[f2[i]]); //主件+附件2

updata(A[i]+A[f1[i]]+A[f2[i]],C[i]+C[f1[i]]+C[f2[i]]);//主件+附件1+附件2

end;

end;

end;

writeln(dp[m]);

readln(n);

end.

{可以看见这种方法并不适合推广的情况...}

program t10166;

var

fin,fout:text;

s,n,p:longint;

v,w,son,data:array[0..70]of longint;

map:array[0..70,0..70]of longint;

rec:array[0..70,0..3210]of longint;

used:array[0..70,0..3210]of boolean;

function dfs(a:longint):longint;

var

i:longint;

begin

data[p]:=a;

p:=p+1;

if map[a,0]=0

then begin

son[a]:=1;

exit(1);

end;

for i:=1 to map[a,0] do

inc(son[a],dfs(map[a,i]));

inc(son[a]);

exit(son[a]);

end;

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

begin

if a>b then exit(a) else exit(b);

end;

function f(i,j:longint):longint;

begin

if i=n+1 then exit(0);

if used then exit(rec);

used:=true;

rec:=f(i+son[data[i]],j);

if j-v[data[i]]>=0 then rec:=max(rec,f(i+1,j-v[data[i]])+w[data[i]]*v[data[i]]);

exit(rec);

end;

procedure dp;

var

i,t:longint;

begin

read(fin,s,n);

s:=s div 10;

for i:=1 to n do

begin

read(fin,v[i],w[i],t);

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

inc(map[t,0]);

map[t,map[t,0]]:=i;

end;

dfs(0);

writeln(fout,f(1,s)*10);

end;

begin

assign(fin,'t10166.in');

assign(fout,'t10166.out');

reset(fin);

rewrite(fout);

dp;

close(fin);

close(fout);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于AC了

提交了N遍都只有10分。。。。。

原来所谓主件编号是指所有物品中的第几个物品，而非仅指主件……

大家别被题目骗了。。。

方程 f=max(f,只取主件，主件+附件1，主件+附件2，主件+附件2+附件2)；

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于AC了

提交了N遍都只有10分。。。。。

原来所谓主件编号是指所有物品中的第几个物品，而非仅指主件……

大家别被题目骗了。。。

编译通过...

├ 测试数据 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

原来附件也是占用编号的,弄得我提交了三次才过,郁闷，题意不清

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

分组01背包

调试了相当久的说……= -。。。变量那么多老弄混

不过是一次AC^^ 整理为0/1背包，注意判断0/1时是否V会小于0

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

uses math;

const

maxn = 60; maxm = 3200;

var

i, j, k, n, m, ans : longint;

f : array[0..maxn, 0..maxm] of longint;

w, fa : array[1..maxn] of longint;

val, v : array[1..maxn, 0..4] of longint;

procedure prepare;

var

i, j : longint;

begin

for i:= 1 to n do

if fa[i] = 0 then val[i, 1]:= v[i, 1] * w[i]

else

if val[fa[i], 2] = 0 then

begin

val[fa[i], 2]:= val[fa[i], 1] + v[i, 1] * w[i];

v[fa[i], 2]:= v[fa[i], 1] +v[i, 1];

end else

begin

val[fa[i], 3]:= val[fa[i], 1] + v[i, 1] * w[i];

val[fa[i], 4]:= val[fa[i], 2] + val[fa[i], 3] - v[fa[i], 1] * w[fa[i]];

v[fa[i], 3]:= v[fa[i], 1] + v[i, 1];

v[fa[i], 4]:= v[fa[i], 2] + v[fa[i], 3] - v[fa[i], 1];

end; i:= 1;

repeat

if fa[i] > 0 then

begin

for j:= i + 1 to n do

begin

v[j - 1]:= v[j];val[j - 1]:= val[j];fa[j - 1]:= fa[j];

end;

fillchar(v[n], sizeof(v[n]), 0);

fillchar(val[n], sizeof(val[n]), 0); fa[n]:= 0;

n:= n - 1;

end else i:= i + 1;

until i > n;

end;

{ = = = = = = main = = = = = = }

begin

for i:= 1 to n do begin

readln(v[i, 1], w[i], fa[i]);

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

end;

prepare;

for i:= 1 to n do

for j:= 1 to m do

for k:= 0 to 4 do

if ((k = 0) or (val[i, k] > 0)) and (j >= v[i, k]) then

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

writeln(f[n,m]*10);

end.