HDU1011 Starship Troopers（树形dp）

题意：

有n个房间组成一棵树，你有m个士兵，从1号房间开始让士兵向相邻的房间出发，每个房间里有一个代价，代价是值/20个士兵，

同时有一个价值，问你花费这m个士兵可以得到的最大价值是多少，

思路：

dp[i][j]记录以节点i为根节点，j个士兵时所能够获得的最大价值

/* *********************************************** Author :devil Created Time :2016/3/23 15:33:24 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; #define N 110 int dp[N][N],val[N],bug[N]; bool vis[N]; vector<int>eg[N]; int n,m; void init() {memset(dp,0,sizeof(dp));memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++)eg[i].clear(); } void dfs(int u) {vis[u]=true;int need=(bug[u]+19)/20;for(int i=need;i<=m;i++)dp[u][i]=val[u];for(int i=0;i<eg[u].size();i++){int to=eg[u][i];if(vis[to]) continue;dfs(to);for(int j=m;j>=need;j--)for(int k=1;k+need<=j;k++)dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[to][k]);} } int main() {//freopen("in.txt","r",stdin);int x,y;while(~scanf("%d%d",&n,&m)&&n!=-1){init();for(int i=1; i<=n; i++)scanf("%d%d",&bug[i],&val[i]);for(int i=1; i<n; i++){scanf("%d%d",&x,&y);eg[x].push_back(y);eg[y].push_back(x);}if(!m) printf("0\n");else{dfs(1);printf("%d\n",dp[1][m]);}}return 0; }

 

转载于:https://www.cnblogs.com/d-e-v-i-l/p/5311388.html

总结

以上是生活随笔为你收集整理的HDU1011 Starship Troopers（树形dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。