本文主要是介绍hdu1011，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
树形dp背包
对任一节点，取得最大值相当于在确定根节点消耗之后对所有子树进行01背包，获得1~m每个状态的最大值，然后向上递归，直至找到根节点，此时求得的最大值即为所求
状态转移方程：dp[i][t]=max(dp[i][t],dp[i][k]+dp[son[i]][t-k])(k=0,1,2......)
#include <iostream>using namespace std;int map[105][105];
int v[105];
int w[105];
int dp[105][105];
int n,m;void build(int s) //建树，此题比较坑的地方，即给的节点不一定是先父节点后子节点的顺序
{for (int i=1;i<=n;i++){if (map[s][i]==1){map[i][s]=0;build(i);}}
}int max(int a,int b)
{return a>b?a:b;
}void get(int s)
{for (int i=w[s];i<=m;i++)dp[s][i]=v[s];for (int i=1;i<=n;i++){if (map[s][i]==1){get(i);for (int t=m;t>w[s];t--){for (int k=t-1;k>=w[s];k--){dp[s][t]=max(dp[s][t],dp[s][k]+dp[i][t-k]);}}}}
}int main()
{while (scanf("%d%d",&n,&m)&&n!=-1){memset(map,0,sizeof(map));memset(dp,0,sizeof(dp));for (int i=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);w[i]=(w[i]+19)/20;}for (int i=1;i<n;i++){int k,t;scanf("%d%d",&k,&t);map[k][t]=map[t][k]=1;}build(1);get(1);if (m==0)cout<<0<<endl;elsecout<<dp[1][m]<<endl;}
}这篇关于hdu1011的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
