首页 > 代码库 > HDU 1011 Starship Troopers
HDU 1011 Starship Troopers
这算是 经典的树形DP 入门题吧：
题目的意思： 一个由N个点形成的树状网络；进入点是1；现在每个节点
有俩个属性 1：防守的人数，2 打败防守人数的奖励；
问由N个人组队去赚钱 最多赚多少：注一个人可以打败20个防守渣渣（这就是传说中的战五渣）！对于需要的人数取ceil（）；
很经典的 依赖性的背包； dp[i][j] ( 节点i 为跟 有J个士兵 可以得到多少奖励 ) 这道题 有坑点不要写错！假如一个节点的的防守人数是0， 你不必 在这个节点留人，但是必须有人经过这点；
#include <cstring>#include <algorithm>#include <cstdio>#include <cmath>#include <cstdlib>#include <iostream>#include <map>#include <string>using namespace std;const int maxn=101;struct Edge{ int to,pre; Edge(){} Edge(int to,int pre):to(to),pre(pre){}};struct info{ int bug,money; info(){} void input() { scanf("%d%d",&bug,&money); bug=(bug+19)/20; }};info ko[maxn];Edge edge[maxn*2+1];int head[maxn],pos;int dp[maxn][maxn];void inint(){ pos=0; memset(dp,0,sizeof(dp)); memset(head,-1,sizeof head);}void add_edge(int s,int to){ edge[pos]=Edge(to,head[s]); head[s]=pos++;}int n,m;void dfs(int &fa,int &s){ for(int i=ko[s].bug;i<=m;i++) dp[s][i]=ko[s].money; for(int i=head[s];~i;i=edge[i].pre) { Edge & tmp=edge[i]; if(tmp.to==fa)continue; dfs(s,tmp.to);
//根节点是必须取，所以W>ko[s].bug；for(int w=m;w>ko[s].bug;w--)for(int j=ko[s].bug;j<w;j++)dp[s][w]=max(dp[s][w],dp[s][j]+dp[tmp.to][w-j]); }}int main(){ int a,b; while(~scanf("%d%d",&n,&m)) { inint(); if(n==-1&&m==-1) return 0; for(int i=1;i<=n;i++)ko[i].input(); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } a=-1,b=1; dfs(a,b); if(m==0){printf("%d\n",0);continue;} printf("%d\n",dp[1][m]); }}
HDU 1011 Starship Troopers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。