hdu1561 树形dp

生活随笔 收集整理的这篇文章主要介绍了 hdu1561 树形dp 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题意：
      给你n个东西，每个东西有自己的价值，让你从里面最多取出m个物品，问最大的价值，有的物品有限制，就是必须先取出某个物品后才能取出这个物品。

思路：

      树形dp，应该是树形的01背包吧，自己dp太渣了，看题解看了好久才懂，我对于树形dp的理解目前是 树形第dp就是用树的节点关系，来约束dp更新是的顺序，比如必须更新完子节点才能更新父节点什么的，对于这个题目，我们首先把给的限制关系建立成一个树，取a之前必须取b，那么 add(b ,a),然后开两个数组dp[i][j] 表示的是 以第i个为根节点的时候取了j个物品的最优值tmp[i][j] 则是dp的一个临时值，目的是为了先更新i为根节点的所有子节点，然后在强制吧i加进去，整体的思路就是先更新后面的（后面的就是前面有很长限制的）然后在更新前面的，前面的每一个都是强制更新进去的，保证了正确性，具体看代码。

#include<stdio.h> #include<string.h>#define N 200 + 10 typedef struct {int to ,next; }STAR;STAR E[N]; int list[N] ,tot; int mark[N] ,cost[N]; int dp[N][N] ,tmp[N][N];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int maxx(int x ,int y) {return x > y ? x : y; }void DFS(int root ,int m) {mark[root] = 1;for(int k = list[root] ;k ;k = E[k].next){int to = E[k].to;if(mark[to]) continue;DFS(to ,m);for(int i = m ;i >= 0 ;i --)for(int j = 0 ;j <= i ;j ++)tmp[root][i] = maxx(tmp[root][i] ,tmp[root][i-j] + dp[to][j]);}for(int i = 1 ;i <= m + 1 ;i ++)dp[root][i] = tmp[root][i-1] + cost[root]; }int main () {int i ,n ,m ,a ,b;while(~scanf("%d %d" ,&n ,&m) && n + m){memset(list ,0 ,sizeof(list)) ,tot = 1;memset(mark ,0 ,sizeof(mark));memset(tmp ,0 ,sizeof(tmp));memset(dp ,0 ,sizeof(dp));for(i = 1 ;i <= n ;i ++){scanf("%d %d" ,&a ,&b);add(a ,i);cost[i] = b;}DFS(0 ,m);printf("%d\n" ,dp[0][m+1]);}return 0; }

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

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

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

网址：hdu1561 树形dp https://m.mxgxt.com/news/view/1965443

相关内容

hdu4126(MST + 树形dp
dp ... 什么意思 dp是什么 ... 术语
DP
饭圈用语dp是什么意思 常见饭圈缩写dp的含义
饭圈用语dp是什么意思 类似dp的网络术语有哪些
怎么理解饭圈dp，何谓“饭圈”
怎么理解饭圈dp
dp是什么意思网络术语，饭圈（带领粉丝围攻黑粉）
主持人杨阳专访明星网红造型店DP国际创始人陈有军
openoj的一个小比赛（F题解题报告）poj3978(dp+素数筛选）

随便看看