本文主要是介绍HDU 1011 Starship Troopers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
人一我百，人十我万！！
树形DP加上一些背包的思想，有一些模板的感觉。
ac code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)typedef long long LL;
const int N=1100001;
const int M=6666666;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
vector <int > V[106];
int dp[106][106];
int m,n;
struct p
{int bug,brain;
}a[106];void dfs(int u,int pre)
{for(int i=a[u].bug;i<=m;i++)dp[u][i]=a[u].brain;//赋值，一开始这里没有想清楚，卡了好久for(int i=0;i<V[u].size();i++){int v=V[u][i];if(v==pre) continue;dfs(v,u);for(int j=m;j>=a[u].bug;j--){for(int k=1;k<=j-a[u].bug;k++)if(dp[u][j]<dp[v][k]+dp[u][j-k])//背包的思想，求最大的值dp[u][j]=dp[v][k]+dp[u][j-k];}}
}int main()
{while(~si2(n,m)&&n!=-1&&m!=-1){ford(i,1,n){V[i].clear();si2(a[i].bug,a[i].brain);a[i].bug=(a[i].bug+19)/20;//进行简单处理}forb(i,1,n){int u,v;si2(u,v);V[u].push_back(v);V[v].push_back(u);}if(m==0){printf("0\n");continue;}mset(dp,0);dfs(1,-1);printf("%d\n",dp[1][m]);}return 0;
}
这篇关于HDU 1011 Starship Troopers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
