Description
DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA (Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如，Sange and Yasha的合成需要Sange, Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt of Giant Strength 和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某些性价比很高的装备。现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗？他会教你魔法Haunt（幽灵附体）作为回报的。Input输入文件第一行包含两个整数，N (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分别表示装备的种类数和金币数。装备用1到N的整数编号。接下来的N行，按照装备1到装备n的顺序，每行描述一种装备。每一行的第一个正整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的种类和需要的个数。Output第一行包含一个整数S，表示最多可以提升多少点力量值。Sample Input10 595 A 3 6 1 9 2 10 11 B 5 31 B 4 31 B 2 38 A 3 2 1 3 1 7 11 B 5 35 B 3 315 A 3 1 1 5 1 4 11 B 3 51 B 4 3Sample Output33
看见我机房的小伙伴没写，我又不能问他，BZOJ上这又不是一道不可做题，不想跳过这道题，于是就写了
题解一共也就两种，一个是VFleaKing的，另一个是普通的树dp
看题解看不懂啊，囧，没办法，我就是这么弱........
于是先打暴力，f[i,j,k]表示节点i买了j个，用了k元钱的最大力量值
然后树dp之，对于每一个j，先强制买好j个i物品，然后k元钱里剩下的去做背包（从i的儿子里面选，用合成剩余的部分来做01背包）
暴力好不容易打出来（细节没注意，囧，写了一两个小时暴力，之前还想抄C++代码，可惜不怎么懂，勉强翻译过来连样例都过不了）
暴力肯定是要超时的（我自测，有的点100s都跑不出），不过我发现了一个优化
1 const 2 maxn=52; 3 maxm=2001; 4 var 5 w,gold,lim,num,max1,fa,first:array[0..maxn]of longint; 6 next,last:array[0..maxn*2]of longint; 7 f:array[0..maxn,0..101,0..maxm]of longint; 8 n,m,ans,tot:longint; 9 10 procedure insert(x,y,z:longint); 11 begin 12 inc(tot); 13 last[tot]:=y; 14 next[tot]:=first[x]; 15 first[x]:=tot; 16 num[tot]:=z; 17 fa[y]:=x; 18 end; 19 20 function max(x,y:longint):longint; 21 begin 22 if x>y then exit(x); 23 exit(y); 24 end; 25 26 function min(x,y:longint):longint; 27 begin 28 if x0 do 49 begin 50 dfs(last[i]); 51 max1[x]:=min(max1[x],max1[last[i]] div num[i]); 52 inc(gold[x],num[i]*gold[last[i]]); 53 i:=next[i]; 54 end; 55 for i:=0 to max1[x] do 56 begin 57 l:=first[x]; 58 for j:=i*gold[x] to m do 59 f[x,i,j]:=w[x]*i; 60 l:=first[x]; 61 while l<>0 do 62 begin 63 for j:=m downto i*gold[x] do 64 for k:=num[l]*i to max1[last[l]] do 65 for v:=(k-num[l]*i)*gold[last[l]] to j-i*gold[x] do 66 f[x,i,j]:=max(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+num[l]*i*gold[last[l]]]-num[l]*i*w[last[l]]); 67 l:=next[l]; 68 end; 69 for j:=i*gold[x] to m do 70 ans:=max(ans,f[x,i,j]); 71 end; 72 end; 73 74 procedure main; 75 var 76 i,j,k,x,y:longint; 77 s:char; 78 begin 79 read(n,m); 80 for i:=1 to n do 81 begin 82 read(w[i]); 83 read(s,s); 84 if s='B' then read(gold[i],lim[i]) 85 else 86 begin 87 read(k); 88 for j:=1 to k do 89 begin 90 read(x,y); 91 insert(i,x,y); 92 end; 93 end; 94 end; 95 for i:=1 to n do 96 if fa[i]=0 then dfs(i); 97 writeln(ans); 98 end; 99 100 begin101 main;102 end.
1 for j:=m downto i*gold[x] do2 for k:=num[l]*i to max1[last[l]] do3 for v:=(k-num[l]*i)*gold[last[l]] to j-i*gold[x] do4 f[x,i,j]:=max(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+num[l]*i*gold[last[l]]]-num[l]*i*w[last[l]]);
在这里，我们枚举的太多，其实只要满足k>=num[l]*i就行了
于是我们做完后可以对f数组做一些处理，使f数组的f[i,j,k]表示i物品买了j个以上，用了k元钱的最大力量
所以每次做完，我们都做一遍下面这个处理
1 for k:=max1[x] downto 1 do2 for v:=gold[x]*k to m do3 up(f[x,k-1,v],f[x,k,v]);
只不过做完这个，我就想不出什么优化了，卡了好久，用cena自测总时间20s左右，BZOJ上就是过不了
过了好久，期间想过各种底层优化，可惜不懂，所以就没写了
然后发现一个很无语的优化，自测总时间6s多
对于每一个点，计算一下这颗子树最多用多少钱，记为lim[x]，这样就不用每次都枚举到m了
1 /************************************************************** 2 Problem: 1017 3 User: 1997cb 4 Language: Pascal 5 Result: Accepted 6 Time:17432 ms 7 Memory:42504 kb 8 ****************************************************************/ 9 10 const 11 maxn=52; 12 maxm=2001; 13 var 14 w,gold,num,max1,fa,first,lim:array[0..maxn]of longint; 15 next,last:array[0..maxn*2]of longint; 16 f:array[0..maxn,0..101,0..maxm]of longint; 17 n,m,ans,tot:longint; 18 19 procedure insert(x,y,z:longint); 20 begin 21 inc(tot); 22 last[tot]:=y; 23 next[tot]:=first[x]; 24 first[x]:=tot; 25 num[tot]:=z; 26 fa[y]:=x; 27 end; 28 29 procedure up(var x:longint;y:longint); 30 begin 31 if xy then x:=y; 37 end; 38 39 procedure dfs(x:longint); 40 var 41 i,j,k,l,v:longint; 42 begin 43 if first[x]=0 then 44 begin 45 down(max1[x],trunc(m/gold[x])); 46 lim[x]:=max1[x]*gold[x]; 47 for i:=1 to max1[x] do 48 f[x,i,i*gold[x]]:=w[x]*i; 49 for k:=max1[x] downto 1 do 50 for v:=gold[x]*k to m do 51 up(f[x,k-1,v],f[x,k,v]); 52 exit; 53 end; 54 max1[x]:=maxm; 55 i:=first[x]; 56 while i<>0 do 57 begin 58 dfs(last[i]); 59 inc(lim[x],lim[last[i]]); 60 down(max1[x],trunc(max1[last[i]]/num[i])); 61 inc(gold[x],num[i]*gold[last[i]]); 62 i:=next[i]; 63 end; 64 down(lim[x],m); 65 for i:=0 to max1[x] do 66 begin 67 l:=first[x]; 68 for j:=i*gold[x] to lim[x] do 69 f[x,i,j]:=w[x]*i; 70 l:=first[x]; 71 while l<>0 do 72 begin 73 k:=num[l]*i; 74 for j:=lim[x] downto i*gold[x] do 75 for v:=0 to j-i*gold[x] do 76 up(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+k*gold[last[l]]]-k*w[last[l]]); 77 l:=next[l]; 78 end; 79 for k:=max1[x] downto 1 do 80 for v:=gold[x]*k to lim[x] do 81 up(f[x,k-1,v],f[x,k,v]); 82 end; 83 end; 84 85 procedure main; 86 var 87 i,j,k,x,y:longint; 88 s:char; 89 begin 90 read(n,m); 91 for i:=1 to n do 92 begin 93 read(w[i]); 94 read(s,s); 95 if s='B' then read(gold[i],max1[i]) 96 else 97 begin 98 read(k); 99 for j:=1 to k do100 begin101 read(x,y);102 insert(i,x,y);103 end;104 end;105 end;106 for i:=1 to n do107 if fa[i]=0 then108 begin109 dfs(i);110 for j:=0 to max1[i] do111 up(ans,f[i,j,lim[i]]);112 end;113 writeln(ans);114 end;115 116 begin117 main;118 end.