本文主要是介绍hdu-1011- Starship Troopers-自由树转二叉树+树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目很水，但是有很多易错点。。。
注意：
1，题目输入的时候是自由树，无向边。
2，如果某个点的bugs是0，也必须有至少一个士兵经过此点。
做法:：
按照题意，把自由树转为二叉树。
然后树形dp
dp[x][y]:在二叉树中的x节点为根的树中，使用了y个士兵获得的最大值。
dp[x][y]=dp[node[x].l][k]+nval[x]+dp[node[x].r][y-k];
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#define INF 99999999
#define MAXN 111
using namespace std;
struct list
{int l,r;
} node[MAXN];
int nval[MAXN],nuse[MAXN];
int n,m;
int dp[111][111];
int dos(int x,int val)
{if(val==0)return 0;if(x==-1)return 0;if(dp[x][val]!=-1)return dp[x][val];int mx=0;mx=max(mx,dos(node[x].r,val));int as,bs;for(int i=0; i<=val; i++){as=i;bs=val-as;if(as>=nuse[x]&&(as!=0))mx=max(mx,dos(node[x].r,bs)+nval[x]+dos(node[x].l,as-nuse[x]));}dp[x][val]=mx;return mx;
}
vector<int>old[MAXN];
int vis[MAXN];
void change(int x)
{int i,len,a,b;len=old[x].size();vis[x]=1;for(i=0; i<len; i++){if(vis[old[x][i]])continue;a=x;b=old[x][i];node[b].r=node[a].l;node[a].l=b;change(old[x][i]);}
}
int main()
{int i,a,b;while(~scanf("%d%d",&n,&m)){if(n==-1&&m==-1)break;memset(dp,-1,sizeof(dp));memset(vis,0,sizeof(vis));for(i=1; i<=n; i++){scanf("%d%d",&a,&b);a=(a+19)/20;nuse[i]=a;nval[i]=b;node[i].l=node[i].r=-1;old[i].clear();}for(i=1; i<n; i++){scanf("%d%d",&a,&b);old[a].push_back(b);old[b].push_back(a);}change(1);cout<<dos(1,m)<<endl;}return 0;
}这篇关于hdu-1011- Starship Troopers-自由树转二叉树+树形DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
