?

?

?

題意：給一個森林，n個節(jié)點，每個點有點權，問若從中剛好選擇m個點（選擇某點之前必須先選擇了其父親），使得這m個點權之和最大為多少？

?

思路：

　　比較常規(guī)。就是DFS一次，枚舉在子樹中可能選擇的k個點（注意上限為min（子樹節(jié)點數(shù)，到此子樹最多可選節(jié)點數(shù)）），需要注意的是dp[t][1]必須是點t自己，枚舉的時候必須先選擇t才能選擇t的孩子。但是本題是森林，那么可以建1個虛擬根編號為0（根輸入一模一樣），然后虛擬根的權為0即可，而所要選的數(shù)就變成m+1了。

?

?

?

1 #include <bits/stdc++.h> 2 #define pii pair<int,int> 3 #define max(x,y) (x>y?x:y) 4 #define min(x,y) (x<y?x:y) 5 #define INF 0x3f3f3f3f 6 #define LL long long 7 using namespace std; 8 const int N=210; 9 10 struct node 11 { 12 int from,to,val,next; 13 node(){}; 14 node(int from,int to,int val,int next):from(from),to(to),val(val),next(next){}; 15 }edge[N]; 16 int head[N], n, edge_cnt; 17 void add_node(int from,int to,int val) 18 { 19 edge[edge_cnt]=node(from, to, val, head[from]); 20 head[from]=edge_cnt++; 21 } 22 23 int dp[N][N]; 24 int DFS(int t,int m,int val) 25 { 26 if(m==0) return 0; //點數(shù)上限了。 27 dp[t][1]=val; //只能挑1個點時，必須挑自己 28 node e; 29 int sum=1; 30 for(int i=head[t]; i!=-1&&m>1; i=e.next) 31 { 32 e=edge[i]; 33 int tmp=DFS(e.to, m-1, e.val); //最多可以在e.to子樹中選多少個點 34 sum+=tmp; 35 36 for(int j=sum; j>1; j--) 37 for(int k=1; k<=tmp&& k<j; k++) //保證j-k>=1，因為t是必選的 38 if(dp[t][j-k]>=0) 39 dp[t][j]=max(dp[t][j], dp[t][j-k]+dp[e.to][k]); 40 } 41 return sum; //返回在本子樹中可以選的點數(shù)上限 42 } 43 44 int main() 45 { 46 //freopen("input.txt", "r", stdin); 47 int a,b,m; 48 while(scanf("%d%d",&n,&m),n+m) 49 { 50 memset(head, -1, sizeof(head)); 51 memset(dp, -1, sizeof(dp)); 52 edge_cnt=0; 53 54 for(int i=1; i<=n; i++) 55 { 56 scanf("%d%d",&a,&b); 57 add_node(a,i,b); 58 } 59 DFS(0, m+1, 0); //0是虛擬根 60 printf("%d\n", dp[0][m+1]); 61 } 62 return 0; 63 } AC代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/xcw0754/p/4818842.html

總結

以上是生活随笔為你收集整理的HDU 1561 The more, The Better （树形DP，常规）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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