hdu1561樹形DP入門

hdu1561The More,The Better 推薦題解 dp[ i ] [ j ]  以節點i為跟，取j個（包括i，即dp[i][1]=V[i]）所能得到的最大值 [cpp] #include<iostream>   #include<cstdio>   #include<cstring>   #include<vector>   using namespace std;      int N,M,v[223];   vector<int>son[223];      int dp[223][223];      void dfs(int n,int left){       int i,j,k,len=son[n].size();       dp[n][1]=v[n];       for(i=0;i<len;i++){           if(left>1)   dfs(son[n][i],left-1);           for(j=left;j>=1;j--)               for(k=1;k<=j;k++)                   if(dp[n][j+1]<   dp[n][j+1-k]    +dp[son[n][i]][k])  dp[n][j+1]=dp[n][j+1-k]+dp[son[n][i]][k];       //                          其他兒子的總值     第i個兒子取k個       }   }      int main()   {       int i,j,k;              while(scanf("%d%d",&N,&M),N||M)       {           //           memset(v,0,sizeof(v));           memset(dp,0,sizeof(dp));           for(i=0;i<=N;i++)    son[i].clear();           //           for(i=1;i<=N;i++){               scanf("%d%d",&j,&v[i]);               son[j].push_back(i);           }                      dfs(0,M+1);                      printf("%d\n",dp[0][M+1]);       }       return 0;   }