注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1011 Starship Troopers  

2013-09-03 19:37:56|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1011
一棵树n个结点,每个结点上有两个值,分别表示bugs数量和价值。现在有p个士兵,从结点1开始攻击,一个士兵能攻击20个bugs,把某个结点的bugs都攻击完才能得到结点上的价值,一个士兵只能攻击一个结点,也就是士兵停留在攻击的结点上,走过的结点不能再走,走到一个结点上必须攻击完所有的bugs,否则不能走。问能获得的最大价值。
dfs+树形dp,对每个结点的子节点都dp一遍。
dp[i][j] 表示第i个结点留j个士兵能获得的最大值。
dp[i][j]=max(dp[i][j],dp[t][k]+dp[i][j-k]); t表示i的子节点

/*
* pro.cpp
*
* Created on: 2013-09-03
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
//#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=110;
const int M=150010;
const int MOD=20100501;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

int n,m,res,b[N],val[N],vis[N],dp[N][N];
vector<int> v[N];

void dfs(int tmp)
{
int cost=(b[tmp]+19)/20;
for(int i=cost;i<=m;i++)
dp[tmp][i]=val[tmp];
vis[tmp]=1;
for(int i=0;i<(int)v[tmp].size();i++)
{
int t=v[tmp][i];
if(!vis[t])
{
dfs(t);
for(int j=m;j>=cost;j--)
for(int k=1;k<=j-cost;k++)
dp[tmp][j]=max(dp[tmp][j],dp[t][k]+dp[tmp][j-k]);
}
}
}

void solve()
{
int p,q;
for(int i=0;i<=n;i++)
v[i].clear();
for(int i=1;i<=n;i++)
scanf("%d%d",&b[i],&val[i]);
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&p,&q);
v[p].push_back(q);
v[q].push_back(p);
}
if(m == 0)
{
printf("0\n");
return ;
}
MEM(vis);MEM(dp);
dfs(1);
printf("%d\n",dp[1][m]);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==-1 && m==-1)
break;
solve();
}
return 0;
}



  评论这张
 
阅读(334)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017