比较难想的的一道树形dp。
看到这道题正常的思路应该是$f[i][j][k]$表示i这棵子树里买了j个i物品花费为k的最大收益。
但如果直接这么定义的话转移复杂度会很高，需要枚举j，枚举孩子，枚举k，枚举孩子的花费，还要枚举每个孩子各买了多少件。
想办法把最后一个循环去掉。
重新定义状态$f[i][j][k]$表示表示i这棵子树里至少买了j个i物品花费为k的最大收益。
每次枚举完物品数量后加上这么一句
if(i!=l[x])f[x][i][j]=max(f[x][i][j],f[x][i+1][j]);
l[x]为x的最大数量。
相当于一个后缀最大值。
就可以轻松转移了。
虽然复杂度还是有些高。(貌似存在复杂度更低的算法？)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int f[][][];
int g[][];
int v[],cost[],l[];
int head[],ver[],nxt[],tot,quan[];
void add(int a,int b,int c)
{
tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;quan[tot]=c;return ;
}
bool vis[];
void dfs(int x)
{
if(!head[x])
{
l[x]=min(l[x],m/cost[x]);
for(int i=;i<=l[x];i++)
{
for(int j=;j<=i;j++)
{
f[x][j][i*cost[x]]=i*v[x];
}
}
return ;
}
l[x]=inf;
for(int i=head[x];i;i=nxt[i])
{
dfs(ver[i]);
l[x]=min(l[x],l[ver[i]]/quan[i]);
cost[x]+=cost[ver[i]]*quan[i];
}
l[x]=min(l[x],m/cost[x]);
memset(g,0xcf,sizeof(g));
g[][]=;
for(int i=l[x];i>=;i--)
{
int cnt=;
for(int j=head[x];j;j=nxt[j])
{
cnt++;
for(int k=;k<=m;k++)
{
for(int l=;l<=k;l++)
{
g[cnt][k]=max(g[cnt][k],g[cnt-][l]+f[ver[j]][i*quan[j]][k-l]-v[ver[j]]*(i*quan[j]));
}
}
}
for(int j=;j<=m;j++)
{
f[x][i][j]=g[cnt][j]+i*v[x];
if(i!=l[x])f[x][i][j]=max(f[x][i][j],f[x][i+][j]);
}
} return ;
}
int main()
{
scanf("%d%d",&n,&m);
memset(f,0xcf,sizeof(f));
for(int i=;i<=n;i++)
{
scanf("%d",&v[i]);
char s[];scanf("%s",s);
if(s[]=='A')
{
int num;
int t1,t2;
scanf("%d",&num);
for(int j=;j<=num;j++)
{
scanf("%d%d",&t1,&t2);
vis[t1]=;
add(i,t1,t2);
}
}
else
{
scanf("%d%d",&cost[i],&l[i]);
}
}
int root=;
for(int i=;i<=n;i++)
{
if(!vis[i])add(,i,);
}
dfs(root);
int ans=;
for(int i=;i<=m;i++)ans=max(ans,f[root][][i]);
printf("%d\n",ans);
return ;
}