本文主要是介绍hdu 1561 (树形dp)The more, The Better，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dp的思想方法，就是每个状态有很多个策略，然后怎么选择才是最优的。此时，假设它的所有后续状态的所有最优值已经计算出来。
那么，树形dp同样如此。
当到达一个节点i时，剩下j的容量，总共有x个子节点。假设子节点所有最优值已计算出来。而且已经算出来已经选择了k个子节点时的最优值。算选择第k+1的子节点时：(k+1的子节点有z个儿子,y表示i节点给k+1的子节点y的容量)
dp[i][k+1][j]=max{dp[i][k][j],dp[i][k][j-y]+dp[son[k+1]][z][y]} (1<=y<j)
这个方程表示，给第k+1的子节点y的容量的最大值(此时，k+1子节点所有值已计算出了)加上给前k个节点j-y(此时，i节点的前k个节点所有值也已计算出来)的值是否比原值要大，然后更新。。。
然后，背包理解过的，都知道有个空间优化。j的值从后往前算，可以省掉n。因为总跟上一个节点的状态有关，那么，从后往前算，j减去一个值，还是属于上一个状态的值，。。
dp[i][j]=max{dp[i][j],dp[i][j-y]+dp[son[k]][y]}
总之，就是一个背包问题，每个节点的价值随着花费不同而改变！
#include <iostream>
#include<vector>
using namespace std;int dp[205][205]; //dp[i][j]表示第i个节点有j的背包容量的最大值
vector<int> v[205]; //用来存放每个节点的子节点
int n,m,val[205];int max(int a,int b)
{return a>b?a:b;
}void dfs(int x)
{for(int i=0;i<v[x].size();i++){dfs(v[x][i]); //如果此节点有儿子，那么继续深搜for(int j=m;j>=2;j--) //此节点所有儿子节点做一次背包选择。算出dp[x][j]的最大值。此时，j是背包。for(int k=1;k<j;k++) //儿子节点的背包为j-k，父亲剩余k。 dp[x][j]=max{dp[x][j],dp[x][k]+dp[v[x][i]][j-k];if(dp[x][k]!=-1&&dp[v[x][i]][j-k]!=-1) //这里就是为了避免无谓的计算。因为对于任意一个节点的背包如果多于它整棵树的所有节点，就是浪费。dp[x][j]=max(dp[x][j],dp[x][k]+dp[v[x][i]][j-k]);}
}int main()
{
// freopen("in.txt","r",stdin);int a;while(scanf("%d %d",&n,&m)==2&&(m||n)){for(int i=0;i<=n;i++)v[i].clear(); //每次都要把向量清空。。。谨记！！for(int i=0;i<=n;i++)for(int j=0;j<=m+1;j++)dp[i][j]=-1; //为什么初始化为-1呢，因为这样可以避免无所谓的计算for(int i=1;i<=n;i++){scanf("%d %d",&a,&val[i]);v[a].push_back(i);dp[i][1]=val[i]; //当第i个节点有容量为1时，即只能装它自己，所以值为自己的值。}m++; //把0加进去当做了根节点。所以背包容量要加1。val[0]=dp[0][1]=0; //根节点是加进去的，所以值为0dfs(0);m=m>n?n:m; //如果总的背包容量大于总的节点数时，此时dp[0][m]=-1，所以此时总的背包容量为n。printf("%d\n",dp[0][m]);}return 0;
}
这篇关于hdu 1561 (树形dp)The more, The Better的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
