树上背包
题目传送门
首先，有没有哪位dalao 愿意告诉我为什么合成高级装备不需要附加金币，，
好吧，这个不重要
明确表示装备合成路线可以用一棵树来表示。一颗？傻乎乎的在下之前每次就只dp一棵树，不出意外的WA了，，在看几遍，好嘛，好像是个森林啊（泪奔）
最容易想到的dp[x][i][j]是第x件买了i个，花了j元的最高力量。但是，，这样好像就成为不可做题了（欢迎各路dalao打脸，反正不是我说的[手动滑稽]（偷偷扔出FYJ挡枪）），那么换一种思路，还是dp[x][i][j]，但表示的是第x件装备，用i件合成上级装备（即至少买了i件），花费j元的力量。如果i是基础装备，转移方程就直接出来了：d[x][i][j*cost[x]]=power[x]*(j-i)。
如果是高级装备呢？
那就枚举它买多少件，以及它的子装备买多少件，直接暴力转移，n^2*times^2。看看时限，3s，完全不方
在下代码比较丑，求各位不要介意
#include<bits/stdc++.h>#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>#include<algorithm>#include<queue>#include<deque>#include<list>#include<set>#include<vector>#include<iostream>#define ll int#define re register#define inf 0x3f3f3f3f#define inl inline#define sqr(x) (x*x)//#define eps 1e-8#define debug printf("debug\n");//#pragma comment(linker, "/STACK:1024000000,1024000000")//#pragma GCC optimize (2)//#pragma G++ optimize (2)using namespace std;//const ll mod;const ll MAXN=3e5+10;inl ll read() { ???re ll x = 0; re int f = 1; ???char ch = getchar(); ???while(ch<‘0‘||ch>‘9‘) { if(ch== ‘-‘ ) f = -1; ch = getchar(); } ???while(ch>=‘0‘&&ch<=‘9‘) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} ???return x * f;}inl char readc() { ???char ch=getchar(); ???while((‘z‘<ch||ch<‘a‘)&&(‘Z‘<ch||ch<‘A‘)) ch=getchar(); ???return ch;}inl void write(re ll x){ ???if(x>=10)write(x/10); ???putchar(x%10+‘0‘);}inl void writeln(re ll x){ ???if(x<0) {x=-x;putchar(‘-‘);} ???write(x); puts("");}inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;}inl void FR() { ???freopen(".in","r",stdin); ???freopen(".out","w",stdout);}inl void FC() { ???fclose(stdin); ???fclose(stdout);}struct Node { ???ll u,v,w,nxt;}e[20005<<1];ll cnt,head[60],ssw[60],g[20005],cost[60],times[60];bool fl[60],in[60],vis[60];ll ans[20005];inl void adde(ll u,ll v,ll w) { ???e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w; ???e[cnt].nxt=head[u];head[u]=cnt;}ll d[60][105][2005],n,m;void dp(ll x) { ???if(vis[x]) return ;vis[x]=1; ???if(!fl[x]) {//基础装备 ????????times[x]=min(times[x],m/cost[x]); ???????for(re ll i=times[x];~i;i--) { ???????????for(re ll j=i;j<=times[x];j++) { ???????????????d[x][i][j*cost[x]]=ssw[x]*(j-i); ???????????} ???????} ???????return ; ???} ???for(re ll h=head[x];h;h=e[h].nxt) { ???????dp(e[h].v);cost[x]+=e[h].w*cost[e[h].v]; ???????times[x]=min(times[x],times[e[h].v]/e[h].w); ???} ???times[x]=min(times[x],m/cost[x]); ???for(re ll i=times[x];~i;i--) { ???????for(re ll j=1;j<=m;j++) g[j]=-inf;g[0]=0; ???????for(re ll h=head[x];h;h=e[h].nxt) { ???????????for(re ll k=m;~k;k--) { ???????????????re ll sst=-inf; ???????????????for(re ll l=0;l<=k;l++) {sst=max(sst,g[k-l]+d[e[h].v][i*e[h].w][l]);} ???????????????g[k]=sst;//花k元能到的最高力量 ????????????} ???????} ???????for(re ll j=0;j<=i;j++) { ???????????for(re ll l=0;l<=m;l++) { ???????????????d[x][j][l]=max(d[x][j][l],g[l]+ssw[x]*(i-j)); ???????????} ???????} ???}}int main(){// ???FR(); ???n=read(),m=read(); ???memset(times,inf,sizeof(times)); ???memset(d,-inf,sizeof(d)); ???for(re ll i=1;i<=n;i++) { ???????ssw[i]=read(); ???????char sj[3];scanf("%s",sj); ???????if(sj[0]==‘A‘) { ???????????fl[i]=1;re ll c=read(); ???????????for(re ll j=1;j<=c;j++) { ???????????????re ll sx=read(),xs=read(); ???????????????if(!in[sx]) in[sx]=1; ???????????????adde(i,sx,xs); ???????????} ???????} ???????else if(sj[0]==‘B‘) { ???????????fl[i]=0;cost[i]=read(); ???????????times[i]=read(); ???????} ???????else puts("RE"); ???} ???for(re ll i=1;i<=n;i++) { ???????if(!in[i]) {//被坑无数次 ????????????dp(i); ???????????for(re ll j=m;~j;j--) { ???????????????for(re ll k=0;k<=j;k++) { ???????????????????ans[j]=max(ans[j],ans[j-k]+d[i][0][k]); ???????????????} ???????????} ???????} ???} ???writeln(ans[m]);// ???FC(); ???return 0;}[JSOI2008]魔兽地图
原文地址：https://www.cnblogs.com/20020723YJX/p/9348020.html