Description
DotR里面的英雄只有一个属性——力量。
他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。
装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本
装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。
比如，Sange and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt
of Giant Strength和 Sange Recipe Scroll合成。
每件基本装备都有数量限制，这限制了你不能无限制地合成某些性价比很高的装备。
现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他吗？他会教你魔法Haunt（幽灵附体）作为回报的。
(1 <= n <= 51) 和 m (0 <= m <= 2,000)
Solution
一道搁置了很久的神题。
一看过去，一棵树形合成路线，子树的选择与能否合成根有关，而且要分配一个金币，最终获得最高收益。而且还有物品的限制。
所以，就是一道树形依赖背包题目了。
但是状态不是很好设，因为子树根的装备可能留下，也可能等着合成更高级的装备。
所以状态中必须要记录i根节点的子树，合成多少个i要用于上面的合成
设f[i][j][k]表示，以i为根的子树，合成j个i用于上面的合成，总共花费k元钱，也就是购买叶子花费k元。
转移的时候，
先把每个子树的答案算出来。
回溯到x后，外层枚举l表示合成几个x
然后依次选择每个子树，用树形背包。
注意，这里每个子树都要选择合成至少l*need[y]个，need[x]表示x合成一个父亲所需要的个数。
所以，不能像一般的背包，每个子树都要选择。
用分组背包，g[tot][j]表示，考虑了前tot个子树，花费j元钱，得到的最大力量。（每个子树都满足至少有l*need[y]）个
g[tot][j]=max(g[tot-1][j-k]+f[y][l*nd[y]][k])
统计完了之后，
再枚举一个j，表示，l中留下j个合成x上一层的装备。
f[x][j][k]=max(g[tot][k]+(l-j)*P[x])
要注意的是，为了保证用了l*nd[y]个，必须令g，f初值是-inf
0肯定是不行的。那就可能会用少于l*nd[y]的钱就合成了l*nd个，虽然总力量是0，但是也可能是一个最优解。
有的时候，为了转移合法，必须把初值设置为极大或者极小值。
这样，每次的最优解，就必定会从这里出来。
可以顺便dp一下合成每个x所需要的价值，以及x合成的上限，可以减少循环的长度。
Code
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int M=2000+3;const int N=55;const int inf=0x3f3f3f3f;int n,m;int ???L[N],P[N],C[N];int nd[N];bool ba[N];struct node{ ???int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){ ???e[++cnt].nxt=hd[x]; ???e[cnt].to=y; ???hd[x]=cnt;}void dp(int x){ ???if(ba[x]){ ???????L[x]=min(L[x],m/C[x]); ???????return; ???} ???for(int i=hd[x];i;i=e[i].nxt){ ???????int y=e[i].to; ???????dp(y); ???????C[x]+=C[y]*nd[y]; ???????L[x]=min(L[x],L[y]/nd[y]); ???} ???L[x]=min(L[x],m/C[x]); ???}int f[N][105][M];int g[N][M];int rt;bool du[N];void dfs(int x){ ???if(ba[x]){ ???????for(int l=0;l<=L[x];l++){ ???????????for(int j=0;j<=l;j++){ ???????????????f[x][j][l*C[x]]=P[x]*(l-j); ???????????} ???????} ???????return ; ???} ???????for(int i=hd[x];i;i=e[i].nxt){ ???????int y=e[i].to; ????????dfs(y); ???} ???????????for(int l=0;l<=L[x];l++){ ???????int now=0; ???????for(int i=hd[x];i;i=e[i].nxt){ ???????????int y=e[i].to; ???????????now++; ???????????memset(g[now],-0x3f,sizeof g[now]); ???????????for(int j=0;j<=m;j++){ ????????????????for(int k=0;k<=j;k++){ ???????????????????g[now][j]=max(g[now][j],g[now-1][j-k]+f[y][l*nd[y]][k]); ???????????????} ???????????} ???????????????} ???????for(int h=0;h<=l;h++){ ???????????for(int k=0;k<=m;k++){ ???????????????if(g[now][k]+(l-h)*P[x]>f[x][h][k]) { ???????????????f[x][h][k]=g[now][k]+(l-h)*P[x]; ???????????????????????????????} ????????????????????????????} ???????} ???}}int main(){ ???scanf("%d%d",&n,&m); ???char op;int s; ???memset(L,inf,sizeof L); ???for(int i=1;i<=n;i++){ ???????scanf("%d ",&P[i]); ???????op=getchar(); ???????if(op==‘B‘){ ???????????ba[i]=1;//is a leaf ???????????du[i]=1; ???????????scanf("%d%d",&C[i],&L[i]); ???????} ???????else{ ???????????scanf("%d",&s); ???????????int son; ???????????for(int j=1;j<=s;j++){ ???????????????scanf("%d",&son); ???????????????scanf("%d",&nd[son]); ???????????????du[son]=1; ???????????????add(i,son); ???????????} ???????} ???} ???????for(int i=1;i<=n;i++) if(!du[i]) rt=i; ???????????dp(rt); ???????memset(f,-inf,sizeof f); ???dfs(rt); ???int ans=0; ???for(int j=0;j<=L[rt];j++){ ???????for(int k=0;k<=m;k++){ ???????????ans=max(ans,f[rt][j][k]); ???????} ???} ???printf("%d",ans); ???return 0;} [JSOI2008]魔兽地图
原文地址：https://www.cnblogs.com/Miracevin/p/9570548.html