hdu 1011 Starship Troopers(树形dp)

题意：

给出一棵树，树上的每个节点都有一个价值，但是要获得这个价值就必须要派出对应多的人数，入口是点1，问得到的最大价值是什么。

题解：

树形背包（01），状态：dp[i][j] 表示根节点i有j个士兵能获得的最大的价值。  枚举孩子树中节点士兵的个数。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define oo 1000001
#define maxn 105
int dp[maxn][maxn];
struct Node
{
int v,next;
}E[maxn<<1];
int head[maxn],tol;
int val[maxn],bugs[maxn];
int n,m;
void inst()
{
memset(head,-1,sizeof head);
tol=0;
memset(dp,0,sizeof dp);
}
void add_edge(int u,int v)
{
E[tol].v=v;
E[tol].next=head[u];
head[u]=tol++;
}
void tree_dp(int u,int pre)
{
int w=(bugs[u]+19)/20;//至少要w的士兵所以dp[u][w]肯定要等于val[u]
for(int i=w;i<=m;i++)
dp[u][i]=val[u];//但是题目说的是至少也就是说我可以将大于w的士兵也放到这个洞里（相当于浪费士兵），自然得到的价值只能是这个洞的价值
for(int i=head[u];i!=-1;i=E[i].next)
{
int v=E[i].v;
if(v==pre) continue;
tree_dp(v,u);
//对于重量从m到w，然后枚举儿子子树的重量不断跟更新（有点像区间dp的区间更新，这个是在树上的分割更新）
for(int j=m;j>=w;j--)
for(int k=1;k<=j-w;k++)
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
int main()
{
int u,v;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==-1&&m==-1) break;
inst();
for(int i=1;i<=n;i++)
scanf("%d %d",&bugs[i],&val[i]);
for(int i=1;i<=n-1;i++)
{
scanf("%d %d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
if(m==0){printf("0n");continue;}
tree_dp(1,-1);
printf("%dn",dp[1][m]);
}
return 0;
}
/*
dp[fa][j]=max{dp[fa][j-k]+dp[son][k]}
5 0
50 10
40 10
40 20
65 30
70 30
1 2
1 3
2 4
2 5
1 0
20 7
5 2
0 1
0 1
0 5
0 1
0 2
1 2
1 3
2 4
2 5
*/

最后

以上就是孤独火车为你收集整理的hdu 1011 Starship Troopers(树形dp)的全部内容，希望文章能够帮你解决hdu 1011 Starship Troopers(树形dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。