思路：

树形DP，和选课那题一模一样。有依赖的背包，也叫做泛化背包。

 

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXD = 3210;const int MAXN = 64;int dp[MAXN][MAXD];int val[MAXN], deg[MAXN], pre[MAXN];void treedp(int u, int vol, int n){
         if (!vol)        return ;    for (int i = 1; i <= n; ++i)    {
             if (pre[i] == u)        {
                 for (int v = 0; v <= vol; ++v)                dp[i][v] = dp[u][v];            treedp(i, vol - val[i], n);            for (int v = vol; v >= val[i]; --v)                dp[u][v] = max(dp[u][v], dp[i][v - val[i]] + val[i] * deg[i]);        }    }}int main(){
         int n, vol;    while (scanf("%d %d", &vol, &n) != EOF)    {
             vol /= 10;        for (int i = 1; i <= n; ++i)            scanf("%d %d %d", &val[i], °[i], &pre[i]), val[i] /= 10;        for (int v = 0; v <= vol; ++v)            dp[0][v] = 0;        treedp(0, vol, n);        printf("%d\n", dp[0][vol] * 10);    }    return 0;}