本文主要是介绍hdu1011（背包树形DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
没有完全理解这题，
m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点
dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解
状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 105
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int dp[N][N],vis[N];
vector<int> mp[N];
int n,m;
struct node
{int x,y;
}s[N];
void dfs(int p){int i,j,k;int temp=ceil(s[p].x/20.0);for(i=temp;i<=m;i++) dp[p][i]=s[p].y;vis[p]=1;for(i = 0; i < mp[p].size();i++){int t = mp[p][i];if(vis[t]) continue;dfs(t);for(j=m;j>=temp;j--){for(k=1; k<=j-temp; k++)//留下temp攻打pdp[p][j]=max(dp[p][j],dp[p][j-k]+dp[t][k]);}}}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);while(cin>>n>>m){if(n == -1 && m == -1) break;int ans = 0;int i;for(i = 0; i <= n; i++)mp[i].clear();memset(dp,0,sizeof(dp));//不一定要恰好装满，所以 初始化为0memset(vis,0,sizeof(vis));for(i = 1; i <= n; i++)cin>>s[i].x>>s[i].y;for(i = 0; i < n-1; i++){int a,b;cin>>a>>b;mp[a].push_back(b);mp[b].push_back(a);}if(m == 0){cout<<0<<endl;continue;}dfs(1);int j;// for(i = 1 ; i <= n; i++){// for(j = 0; j <= m; j++)// cout<<dp[i][j]<<" ";// cout<<endl;//}cout<<dp[1][m]<<endl;}return 0;
}
这篇关于hdu1011（背包树形DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
