看一下题意，树上DP？
然后考虑状态，设 f [ x ] [ k ] 表示在 x 的子树上花费 k 元时获得的最大价值
但是可能当前买的用于更高一层的合成，如果这样不能确定当前买的东西是否够更高一层的合成
所以多一维，设 f [ x ] [ j ] [ k ] ，x,k 意义同上，j 表示装备 x 留了 j 件用于高层合成（此时这 j 件 x 装备还不计入贡献）
然后考虑转移，把子树状态一个个合并进入 f [ x ]
但是发现合并时的 f 表示的东西不是我们设的东西，很不好转移，而且枚举 j 并不能确定当前总共要合成几个 x
所以要枚举 i 表示当前总共合成 i 个 x 装备
考虑设 g [ tot ] [ k ]，表示在保证合成了 i 个 x 装备的情况下，当前枚举到第 tot 个儿子花费 k 元能获得的最大价值
那么容易得到一个转移方程: $g[tot][k]=max(g[tot][k],g[tot-1][k-l]+f[v][w][l])$ （好像就是背包）
$l,w$ 分别为 当前儿子的花费和当前儿子要上交的装备数量，初始 g 为 -INF，g [ 0 ] [ 0 ] = 0
容易发现我们的 g 可以用滚动数组滚掉一维 tot，那就滚掉吧
注意不管是 g 还是 f ，如果不存在方案那么值为 -INF
最后再用 g 来更新 f ，枚举上交数量 j ，总花费 k，设val[ x ] 表示装备 x 的贡献 :
那么$f[x][j][k]=max(f[x][j][k],g[k]+val[x]*(i-j))$，同样初始 f 为-INF
注意上述转移是高级装备 x 的转移，基本装备就直接搞就好了，很简单
注意最后可能是森林，所以要再设一个 h [ k ] 然后对每个树根做一个简单背包
转移不用写了吧
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef unsigned long long ull; inline int read() { int x=0,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; } const int N=57,M=2007,INF=1e9+7; int fir[N],from[M],to[M],num[M],cntt; inline void add(int &a,int &b,int &c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; num[cntt]=c; } int n,m; int p[N],cst[N],val[N],mx[N]; int f[N][N<<1][M],g[M]; void dfs(int x) { if(p[x])//如果是基本装备 { mx[x]=min(mx[x],m/cst[x]);//先算一下最大购买数量 for(int i=0;i<=mx[x];i++)//上交几个 for(int j=i;j<=mx[x];j++)/*买了几个*/ f[x][i][j*cst[x]]=val[x]*(j-i); return; } mx[x]=INF; for(int i=fir[x];i;i=from[i])//先更新子树 { int &v=to[i]; dfs(v); cst[x]+=cst[v]*num[i]; mx[x]=min(mx[x],mx[v]/num[i]);//更新最大购买数量 } mx[x]=min(mx[x],m/cst[x]);//更新最大购买数量 for(int i=0;i<=mx[x];i++)//合成几个 { memset(g,~0x3f,sizeof(g)); g[0]=0; for(int j=fir[x];j;j=from[j])//先把每个儿子并到g里 { int &v=to[j],w=num[j]*i; for(int k=m;k>=0;k--)//总花费,注意倒着枚举 { int t=-INF;//注意如果f[v][w][l]全都不合法的话g[k]也不可能合法，为-INF for(int l=0;l<=k;l++)/*在当前儿子子树上花费*/ t=max(t,g[k-l]+f[v][w][l]); g[k]=t; } } for(int j=0;j<=i;j++)//上交几个 for(int k=0;k<=m;k++)/*总共用了多少钱*/ f[x][j][k]=max(f[x][j][k],g[k]+val[x]*(i-j)); } } int h[M]; bool pd[N]; int main() { memset(f,~0x3f,sizeof(f)); n=read(); m=read(); char ch[5]; int a,b,c; for(int i=1;i<=n;i++) { val[i]=read(); scanf("%s",ch); if(ch[0]=='A') { a=read(); for(int j=1;j<=a;j++) b=read(),c=read(),add(i,b,c),pd[b]=1;//pd判断是否有父节点 } else cst[i]=read(),mx[i]=read(),p[i]=1;//p判断是否是基础装备 } for(int i=1;i<=n;i++)//可能是森林 { if(pd[i]) continue;//只要考虑树根 dfs(i); for(int j=m;j>=0;j--)//总共用了多少钱,注意倒着枚举 for(int k=0;k<=j;k++)/*砸了多少钱到这个树里*/ h[j]=max(h[j],h[j-k]+f[i][0][k]);//就是基础背包 } int ans=0; for(int i=0;i<=m;i++) ans=max(ans,h[i]); printf("%d",ans); return 0; }