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 Input
10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3
Sample Output
33
看见我机房的小伙伴没写，我又不能问他，BZOJ上这又不是一道不可做题，不想跳过这道题，于是就写了
题解一共也就两种，一个是VFleaKing的，另一个是普通的树dp
看题解看不懂啊，囧，没办法，我就是这么弱........
于是先打暴力，f[i,j,k]表示节点i买了j个，用了k元钱的最大力量值
然后树dp之，对于每一个j，先强制买好j个i物品，然后k元钱里剩下的去做背包（从i的儿子里面选，用合成剩余的部分来做01背包）
暴力好不容易打出来（细节没注意，囧，写了一两个小时暴力，之前还想抄C++代码，可惜不怎么懂，勉强翻译过来连样例都过不了）
暴力肯定是要超时的（我自测，有的点100s都跑不出），不过我发现了一个优化
const
maxn=;
maxm=;
var
w,gold,lim,num,max1,fa,first:array[..maxn]of longint;
next,last:array[..maxn*]of longint;
f:array[..maxn,..,..maxm]of longint;
n,m,ans,tot:longint; procedure insert(x,y,z:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
num[tot]:=z;
fa[y]:=x;
end; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure dfs(x:longint);
var
i,j,k,l,v:longint;
begin
if first[x]= then
begin
max1[x]:=min(lim[x],m div gold[x]);
for i:= to max1[x] do
begin
f[x,i,i*gold[x]]:=w[x]*i;
ans:=max(ans,f[x,i,i*gold[x]]);
end;
exit;
end;
max1[x]:=maxm;
i:=first[x];
while i<> do
begin
dfs(last[i]);
max1[x]:=min(max1[x],max1[last[i]] div num[i]);
inc(gold[x],num[i]*gold[last[i]]);
i:=next[i];
end;
for i:= to max1[x] do
begin
l:=first[x];
for j:=i*gold[x] to m do
f[x,i,j]:=w[x]*i;
l:=first[x];
while l<> do
begin
for j:=m downto i*gold[x] do
for k:=num[l]*i to max1[last[l]] do
for v:=(k-num[l]*i)*gold[last[l]] to j-i*gold[x] do
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]]);
l:=next[l];
end;
for j:=i*gold[x] to m do
ans:=max(ans,f[x,i,j]);
end;
end; procedure main;
var
i,j,k,x,y:longint;
s:char;
begin
read(n,m);
for i:= to n do
begin
read(w[i]);
read(s,s);
if s='B' then read(gold[i],lim[i])
else
begin
read(k);
for j:= to k do
begin
read(x,y);
insert(i,x,y);
end;
end;
end;
for i:= to n do
if fa[i]= then dfs(i);
writeln(ans);
end; begin
main;
end.
暴力
for j:=m downto i*gold[x] do
for k:=num[l]*i to max1[last[l]] do
for v:=(k-num[l]*i)*gold[last[l]] to j-i*gold[x] do
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元钱的最大力量
所以每次做完，我们都做一遍下面这个处理
for k:=max1[x] downto do
for v:=gold[x]*k to m do
up(f[x,k-,v],f[x,k,v]);
只不过做完这个，我就想不出什么优化了，卡了好久，用cena自测总时间20s左右，BZOJ上就是过不了
过了好久，期间想过各种底层优化，可惜不懂，所以就没写了
然后发现一个很无语的优化，自测总时间6s多
对于每一个点，计算一下这颗子树最多用多少钱，记为lim[x]，这样就不用每次都枚举到m了
/**************************************************************
Problem:
User: 1997cb
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ const
maxn=;
maxm=;
var
w,gold,num,max1,fa,first,lim:array[..maxn]of longint;
next,last:array[..maxn*]of longint;
f:array[..maxn,..,..maxm]of longint;
n,m,ans,tot:longint; procedure insert(x,y,z:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
num[tot]:=z;
fa[y]:=x;
end; procedure up(var x:longint;y:longint);
begin
if x<y then x:=y;
end; procedure down(var x:longint;y:longint);
begin
if x>y then x:=y;
end; procedure dfs(x:longint);
var
i,j,k,l,v:longint;
begin
if first[x]= then
begin
down(max1[x],trunc(m/gold[x]));
lim[x]:=max1[x]*gold[x];
for i:= to max1[x] do
f[x,i,i*gold[x]]:=w[x]*i;
for k:=max1[x] downto do
for v:=gold[x]*k to m do
up(f[x,k-,v],f[x,k,v]);
exit;
end;
max1[x]:=maxm;
i:=first[x];
while i<> do
begin
dfs(last[i]);
inc(lim[x],lim[last[i]]);
down(max1[x],trunc(max1[last[i]]/num[i]));
inc(gold[x],num[i]*gold[last[i]]);
i:=next[i];
end;
down(lim[x],m);
for i:= to max1[x] do
begin
l:=first[x];
for j:=i*gold[x] to lim[x] do
f[x,i,j]:=w[x]*i;
l:=first[x];
while l<> do
begin
k:=num[l]*i;
for j:=lim[x] downto i*gold[x] do
for v:= to j-i*gold[x] do
up(f[x,i,j],f[x,i,j-v]+f[last[l],k,v+k*gold[last[l]]]-k*w[last[l]]);
l:=next[l];
end;
for k:=max1[x] downto do
for v:=gold[x]*k to lim[x] do
up(f[x,k-,v],f[x,k,v]);
end;
end; procedure main;
var
i,j,k,x,y:longint;
s:char;
begin
read(n,m);
for i:= to n do
begin
read(w[i]);
read(s,s);
if s='B' then read(gold[i],max1[i])
else
begin
read(k);
for j:= to k do
begin
read(x,y);
insert(i,x,y);
end;
end;
end;
for i:= to n do
if fa[i]= then
begin
dfs(i);
for j:= to max1[i] do
up(ans,f[i,j,lim[i]]);
end;
writeln(ans);
end; begin
main;
end.
最终版