??有两类共 \(n\) 种物品，所有物品都有一定的价值。第一类物品每种有一定数量和价格，数量上限为 \(k\)，第二类物品可以通过已有的物品合成得到，每种物品合成的方案可以用树表示，父节点由所有子节点的装备以一定数量合成。给出所有物品及合成方案，求用 \(m\) 个货币最高能获得的价值。
??树形 DP。令物品 \(u\) 的价值是 \(val_u\)，价格（第二类物品的价格定义为所有合成所需物品的价格之和）为 \(cost_u\)，合成物品 \(u\) 需要的物品集是 \(S_u\)，其中需要物品 \(v\) 参与合成的个数是 \(c_{u,v}\)。考虑用 \(dp1_{u,i,j}\) 代表节点 \(u\) 上的装备选取恰好 \(i\) 个时花费 \(j\) 个货币能获取的最高价值，\(dp2_{u,i,j}\) 代表节点 \(u\) 上的装备选取至少 \(i\) 个时花费 \(j\) 个货币能获取的最高价值，则 \(dp1_{u,i},dp2_{u,i}\) 可以看作 01 背包。令背包中无法被选出的价格组合对应的价值为 \(-\infty\)。显然 \(dp2_{u,i,j}=\max_{k=i}^{\infty} dp1_{u,k,j}\)，考虑如何计算 \(dp1_{u,i}\)。
??首先，\(dp1_{u,i}\) 只和 \(dp2_{v}(v \in S_u)\) 有关联。令 \(j=i \cdot c_{u,v}\)，因为要获得 \(i\) 个物品 \(u\) 至少要保证选取 \(j\) 个物品 \(v\)，所以 \(dp1_{u,i}\) 只和 \(dp2_{v,j}\) 有关。而 \(dp1_{u,i}\) 中每一项都需要在每个 \(dp2_{v,j}\) 中选取一个价格，价值的组合求和再加上合成 \(i\) 件物品 \(u\) 带来的额外收益，即 \(val_u-\sum_{v \in S_u}val_v \cdot j\)。其过程相当于把每个 \(dp2_{v,j}\) 的所有价值不为 \(-\infty\) 的项捆绑起来的组合背包问题。用组合背包问题的方式求解，复杂度为 \(O(nkm^2)\)。
??虽然对于这道题的数据范围 \(nkm^2\) 高达 \(2 \cdot 10^{10}\)，但是由于背包的性质，如果每次都只把背包中不为 \(-\infty\) 的位置提取出来枚举可以大大优化常数。令物品 \(u\) 的价格（第二类物品的价格定义为所有合成所需物品的价格之和）为 \(cost_u\)，则 \(dp_{u,i}\) 的背包中所有价值不为 \(-\infty\) 的位置一定分布在 \([i \cdot cost_u,k \cdot cost_u]\)，其在 \(dp_u\) 中形成一个高 \(\le k\)，宽自定义的倒三角在 \(k*m\) 矩阵中的截面。而将两个倒三角形状的背包做一次组合背包，时间消耗至多是全满的情况的 \(1/6\)。同时，构造出两个接近全满的背包做组合背包的情况至少需要 \(7\) 个节点，而且一个背包用过一次就不能再用第二次。这种做法在原网站上的运行时间是 1300ms，但即便如此，笔者也不能保证这个算法一定是正确的。笔者目前认为，正确算法存在与否，以及笔者算法正确与否的可能性都存在。
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int maxn=55,maxm=2e3+5,maxl=105;
ll dp[maxn][maxl][maxm];
int n,m;
struct sub{
int v,c;
sub(int _v,int _c){
v=_v; c=_c;
}
};
vector<sub> e[maxn];
ll val[maxn];
int lim[maxn];
bool vis[maxn];
char s[10];
struct item{
int w; ll v;
item(int _w=0,ll _v=0){
w=_w; v=_v;
}
};
item a[maxm],b[maxm];
void mult(ll x[],ll y[]){
int i,j,t,p=0,q=0;
for (i=0;i<=m;i++){
if (x[i]>-inf/2) a[p++]=item(i,x[i]);
if (y[i]>-inf/2) b[q++]=item(i,y[i]);
}
fill(x,x+m+1,-inf);
for (i=0;i<p;i++) for (j=0;j<q&&(t=a[i].w+b[j].w)<=m;j++)
x[t]=max(x[t],a[i].v+b[j].v);
}
void dfs(int u){
int i,j,v,c;
ll det;
if (!e[u].size()) return;
lim[u]=maxl; det=val[u];
for (i=0;i<e[u].size();i++){
v=e[u][i].v; c=e[u][i].c; dfs(v);
lim[u]=min(lim[u],lim[v]/c);
det-=val[v]*c;
}
for (i=0;i<=lim[u];i++)
dp[u][i][0]=i*det;
for (i=0;i<e[u].size();i++){
v=e[u][i].v; c=e[u][i].c;
for (j=0;j<=lim[u];j++)
mult(dp[u][j],dp[v][j*c]);
}
for (i=lim[u];i>0;i--) for (j=0;j<=m;j++)
dp[u][i-1][j]=max(dp[u][i-1][j],dp[u][i][j]);
}
int main(){
int i,j,k,t;
int v,c;
ll ans;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
for (i=0;i<=n;i++) for (j=0;j<maxl;j++) for (k=0;k<=m;k++)
dp[i][j][k]=-inf;
for (i=1;i<=n;i++){
scanf("%lld%s",&val[i],s);
if (s[0]=='B'){
scanf("%d%d",&c,&lim[i]);
for (j=0;j<=lim[i]&&j*c<=m;j++)
dp[i][j][j*c]=j*val[i];
for (j=lim[i];j>0;j--) for (k=0;k<=m;k++)
dp[i][j-1][k]=max(dp[i][j-1][k],dp[i][j][k]);
}
else {
scanf("%d",&t);
while (t--){
scanf("%d%d",&v,&c);
e[i].push_back(sub(v,c));
vis[v]=true;
}
}
}
for (i=1;i<=n;i++) if (!vis[i])
e[0].push_back(sub(i,1));
dfs(0); ans=0;
for (i=0;i<=m;i++) ans=max(ans,dp[0][0][i]);
printf("%lld\n",ans);
return 0;
}原文：https://www.cnblogs.com/Kilo-5723/p/12219096.html