题解 | #购物单#

#include <bits/stdc++.h>
using namespace std;
const int N = 65;
int h[N],e[N],ne[N],w[N],idx,v[N];
int f[N][3210];
int n,m;
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u){
    for(int i=m;i>=v[u];i--) f[u][i] = w[u];
    //对于每个子节点，可用的体积范围为[0,m-v[u]],将每个节点看作一个物品组，进行分组背包即可
    for(int i=h[u];i!=-1;i=ne[i]){
        int ch = e[i];
        dfs(ch);
        for(int j=m;j>=v[u];j--){
            for(int k=0;k<=j-v[u];k++){
                f[u][j] = max(f[u][j],f[u][j-k]+f[ch][k]);
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    //缩小空间
    m /= 10;
    for(int i=1;i<=n;i++){
        int cost,p,q;
        scanf("%d%d%d",&cost,&p,&q);
        w[i] = p*cost;
        v[i] = cost/10;
        if(q == 0){
		    //虚拟源点，将所有依赖关系转化为一颗依赖树树
            add(0,i);
        }else{
            add(q,i);
        }
    }
    dfs(0);
    cout<<f[0][m];
    return 0;
}