题解：P4037 [JSOI2008] 魔兽地图
hnczy
·
·
题解
一道非常综合的背包题。
我们发现每一个点的选择对它的父亲的合成有影响。
这样的话我们可以尝试把这个因素记下来。
这样的话我们就可以直接用多重背包来写了。
先枚举 $rt$ 的合成数量，在对每一个子树枚举，多重背包更新即可。
这里最好在转移的时候再加一个 $g$ 数组，来记一下在此合成数量的花费为 $i$ 时的最大收益。
每次清空一下即可。
可能有森林的情况，所以要把每一个点都枚举过来。
代码还是比较短的，重要在多重背包的写法，可以借鉴一下。
```c++
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=55,inf =1e9;
int n,m,a[N],b[N],cnt[N],d[N],fa[N],f[55][105][2005],g[2005],ans;
//表示f[u][i][j] u这个子树 i的花费,j用于合成的最大贡献
char c;
void tomax(int &x,int y){if(x<y)x=y;}
vector<pii>e[N];
void dfs(int rt) {
for(auto p:e[rt]) {
int u=p.first,c=p.second;
dfs(u);
cnt[rt]=min(cnt[rt],cnt[u]/c);
b[rt]+=b[u]*c;
}
cnt[rt]=min(cnt[rt],m/b[rt]);
for(int i=0; i<=cnt[rt]; i++){//至多能拥有多少
int now=i*b[rt];
memset(g,0,sizeof g);
for(auto tmp:e[rt]) {
int u=tmp.first,c=i*tmp.second;//需要的数量
for(int k=m; k>=0; k--)
for(int o=0; o<=k; o++)
tomax(g[k],g[k-o]+f[u][c][o]);
}
for(int j=0; j<=i; j++)
for(int k=m; k>=now; k--)
tomax(f[rt][j][k-j*b[rt]],g[k-now]+(i-j)*a[rt]),tomax(ans,f[rt][j][k]);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
cin>>a[i]>>c;
if(c=='A') {
scanf("%d",&d[i]);
cnt[i]=inf;
for(int j=1,num,id; j<=d[i]; j++) {
scanf("%d%d",&id,&num);
e[i].push_back({id,num});
fa[id]=i;
}
} else scanf("%d%d",&b[i],&cnt[i]);
}
for(int i=1;i<=n;i++)if(!fa[i])dfs(i);
cout<<ans;
return 0;
}
```
常数可能有点大，需要加快读才能过。