首页 > 代码库 > [HDU 1561] The more, The Better (树形dp)
[HDU 1561] The more, The Better (树形dp)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1561
题目大意：ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？
设计状态 dp[u][i] 代表以u为根的，选择i个的最大收获
状态转移 dp[u][j+k] = max( dp[u][j+k], dp[u][j]+dp[v][k] );
注意状态转移的写法
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 #include <algorithm> 6 #include <cctype> 7 #include <vector> 8 #include <map> 9 #include <set>10 #include <iterator>11 #include <functional>12 #include <cmath>13 #include <numeric>14 using namespace std;15 16 typedef long long LL;17 18 const int MAX_N = 210;19 struct EDGE{20 int to,next;21 };22 EDGE edge[MAX_N];23 int head[MAX_N],ptr;24 25 void init(){26 memset(head,-1,sizeof(head));27 memset(edge,-1,sizeof(edge));28 ptr = 0;29 }30 31 void add_edge(int from,int to){32 edge[ptr].to = to;33 edge[ptr].next = head[from];34 head[from] = ptr++;35 }36 37 int N,M;38 int val[MAX_N],dp[MAX_N][MAX_N],sum[MAX_N];39 bool vis[MAX_N];40 41 void dfs(int u){42 if( vis[u] ) return;43 vis[u] = true;44 int tot = 0;45 sum[u] = 1;46 47 for(int i=1;i<=M;i++){48 dp[u][i] = val[u];49 }50 51 for(int i=head[u];~i;i=edge[i].next){52 int v = edge[i].to;53 if( vis[v] ) continue;54 tot++;55 dfs(v);56 sum[u] += sum[v];57 }58 59 if( tot == 0 ){60 return;61 }62 63 for(int i=head[u];~i;i=edge[i].next){64 int v = edge[i].to;65 // printf("v = %d\n",v);66 int ub = 1;67 if( u==0 ) ub = 0;68 for(int j=M;j>=ub;j--){69 for(int k=1;k<=sum[v];k++){70 if( j+k<=M ){71 dp[u][j+k] = max(dp[u][j+k],dp[u][j]+dp[v][k]);72 // printf("dp[%d][%d] = dp[%d][%d]+dp[%d][%d]=%d\n",u,j+k,u,j,v,k,dp[u][j]+dp[v][k]);73 }74 }75 }76 }77 }78 79 int main(){80 while( scanf("%d%d",&N,&M)!=EOF ){81 if( N==0&&M==0 ) break;82 init();83 memset(val,0,sizeof(val));84 for(int i=1;i<=N;i++){85 int t;86 scanf("%d%d",&t,&val[i]);87 add_edge(t,i);88 }89 memset(dp,0,sizeof(dp));90 memset(vis,0,sizeof(vis));91 memset(sum,0,sizeof(sum));92 dfs(0);93 printf("%d\n",dp[0][M]);94 }95 return 0;96 }
[HDU 1561] The more, The Better (树形dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。