題意：
? ? ? 給你n個東西，每個東西有自己的價值，讓你從里面最多取出m個物品，問最大的價值，有的物品有限制，就是必須先取出某個物品后才能取出這個物品。


思路：

? ? ? 樹形dp，應(yīng)該是樹形的01背包吧，自己dp太渣了，看題解看了好久才懂，我對于樹形dp的理解目前是 樹形第dp就是用樹的節(jié)點關(guān)系，來約束dp更新是的順序，比如必須更新完子節(jié)點才能更新父節(jié)點什么的，對于這個題目，我們首先把給的限制關(guān)系建立成一個樹，取a之前必須取b，那么 add(b ,a),然后開兩個數(shù)組dp[i][j] 表示的是 以第i個為根節(jié)點的時候取了j個物品的最優(yōu)值tmp[i][j] 則是dp的一個臨時值，目的是為了先更新i為根節(jié)點的所有子節(jié)點，然后在強制吧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; }

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu1561 树形dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。