本文主要是介绍hdu1011(树形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：有n个节点组成一棵树,有m个士兵,必须从1号房间开始攻打,每个洞防御值1价值b,一个士兵只能产生20的伤害,为了拿到这个节点的价值,必须留下一些士兵消灭这个洞的防御值(并且留下的士兵不可以再去攻打其他节点，并且必须攻打了父节点才可以攻打子节点),问这m个士兵可以得到的最大价值是多少
代码：
#include <math.h>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> G[105];
int n,m;
int dp[105][105],num[105],cost[105],used[105];
void dfs(int s){int i,j,k,tmp;used[s]=1;for(i=0;i<G[s].size();i++){tmp=G[s][i];if(G[tmp].size()&&!used[tmp]){dfs(tmp);for(j=m;j>=num[s];j--) //保证父节点一定能被消灭for(k=1;k<=j-num[s];k++) //留下num[s]的值消灭父节点dp[s][j]=max(dp[s][j],dp[s][j-k]+dp[tmp][k]);}}
}
int main(){int i,j,a,b;while(scanf("%d%d",&n,&m)!=EOF){if(n==-1&&m==-1)break;for(i=1;i<=n;i++)G[i].clear();memset(dp,0,sizeof(dp));memset(num,0,sizeof(num));memset(used,0,sizeof(used));for(i=1;i<=n;i++){scanf("%d%d",&a,&b);num[i]=(int)ceil(a*1.0/20);cost[i]=b; //将每个节点的防御和价值先算出来for(j=num[i];j<=m;j++)dp[i][j]=b;}for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a); //双向边}if(m==0){ //m==0时特判puts("0");continue;}dfs(1);printf("%d\n",dp[1][m]);}return 0;
}
这篇关于hdu1011(树形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
