當(dāng)一個節(jié)點被選擇后，它的所有祖先節(jié)點也要被選擇

該條件換一個說法，可以解釋為：只有當(dāng)選擇了一個節(jié)點后，我們才可以選擇它的子節(jié)點。

我們首先建立狀態(tài)f[i][k]，f[i][k]表示以i節(jié)點為根的子樹，在滿足條件一的情況下，選擇至多k的節(jié)點能夠得到的最大權(quán)值。

則可以寫出狀態(tài)轉(zhuǎn)移情況：

• 選擇i節(jié)點：f[i][k]等于w[i]加上所有子節(jié)點選擇k-1個節(jié)點的最大權(quán)值
• 不選擇i節(jié)點：f[i][k] = 0

不選擇i節(jié)點很好處理，那么我們?nèi)绾翁幚磉x擇i節(jié)點時，子節(jié)點的情況？

根據(jù)題目描述，我們知道給定的節(jié)點i可能有多個兒子節(jié)點，不妨假設(shè)其有m個兒子節(jié)點。

則可以表示為，在m個兒子上一共選擇k-1個節(jié)點，使得選擇的節(jié)點權(quán)值之和最大。

舉個例子，比如樣例：

我們在計算f[1][4]時，需要考慮對于以2,3,4分別為根節(jié)點子樹，一共選擇3個節(jié)點，來使得權(quán)值最大。也就是說在2子樹中選擇x個節(jié)點，3子樹中選擇y個節(jié)點，4子樹中選擇z個節(jié)點，使得x+y+z=3。

很顯然，該問題同樣是一個動態(tài)規(guī)劃問題：

建立狀態(tài)g[i][j]，g[i][j]表示前i個兒子選擇j個節(jié)點時最大權(quán)值，則有狀態(tài)轉(zhuǎn)移過程：

g[i][j] = max{g[i - 1][j - k] + f[childId][k] | k = 0 .. j} 時間限制:10000ms 單點時限:1000ms 內(nèi)存限制:256MB

描述

上回說到，小Ho有著一棵灰常好玩的樹玩具！這棵樹玩具是由N個小球和N-1根木棍拼湊而成，這N個小球都被小Ho標(biāo)上了不同的數(shù)字，并且這些數(shù)字都是處于1..N的范圍之內(nèi)，每根木棍都連接著兩個不同的小球，并且保證任意兩個小球間都不存在兩條不同的路徑可以互相到達(dá)。沒錯，這次說的還是這棵樹玩具的故事！

小Ho的樹玩具的質(zhì)量似乎不是很好，短短玩了幾個星期，便掉漆了！

“簡直是一場噩夢！”小Ho拿著樹玩具眼含熱淚道。

“這有什么好憂傷的，自己買點油漆刷一刷不就行了？”小Hi表示不能理解。

“還可以這樣？”小Ho頓時興高采烈了起來，立馬跑出去買回來了油漆，但是小Ho身上的錢卻不夠——于是他只買回了有限的油漆，這些油漆最多能給M個結(jié)點涂上顏色，這就意味著小Ho不能夠?qū)⑺膼鄣臉渫婢咧械拿恳粋€結(jié)點都涂上油漆！

小Ho低頭思索了半天——他既不想只選一部分結(jié)點補漆，也不想找小Hi借錢，但是很快，他想出了一個非常棒的主意：將包含1號結(jié)點的一部分連通的結(jié)點進(jìn)行涂漆（這里的連通指的是這一些涂漆的結(jié)點可以互相到達(dá)并且不會經(jīng)過沒有涂漆的結(jié)點），然后將剩下的結(jié)點拆掉！

那么究竟選擇哪些結(jié)點進(jìn)行涂漆呢？小Ho想了想給每個結(jié)點都評上了分——他希望最后留下來，也就是涂漆了的那些結(jié)點的評分之和可以盡可能的高！

那么，小Ho該如何做呢？

提示一：樹上的動態(tài)規(guī)劃？其實老早就接觸過了吧！

輸入

每個測試點（輸入文件）有且僅有一組測試數(shù)據(jù)。

每組測試數(shù)據(jù)的第一行為兩個整數(shù)N、M，意義如前文所述。

每組測試數(shù)據(jù)的第二行為N個整數(shù)，其中第i個整數(shù)Vi表示標(biāo)號為i的結(jié)點的評分

每組測試數(shù)據(jù)的第3~N+1行，每行分別描述一根木棍，其中第i+1行為兩個整數(shù)Ai，Bi，表示第i根木棍連接的兩個小球的編號。

對于100%的數(shù)據(jù)，滿足N<=10^2，1<=Ai<=N, 1<=Bi<=N, 1<=Vi<=10^3, 1<=M<=N

小Hi的Tip：那些用數(shù)組存儲樹邊的記得要開兩倍大小哦！

輸出

對于每組測試數(shù)據(jù)，輸出一個整數(shù)Ans，表示使得涂漆結(jié)點的評分之和最高可能是多少。

樣例輸入

10 4 370 328 750 930 604 732 159 167 945 210 1 2 2 3 1 4 1 5 4 6 4 7 4 8 6 9 5 10

樣例輸出

2977

當(dāng)一個節(jié)點被選擇后，它的所有祖先節(jié)點也要被選擇

該條件換一個說法，可以解釋為：只有當(dāng)選擇了一個節(jié)點后，我們才可以選擇它的子節(jié)點。

我們首先建立狀態(tài)f[i][k]，f[i][k]表示以i節(jié)點為根的子樹，在滿足條件一的情況下，選擇至多k的節(jié)點能夠得到的最大權(quán)值。

則可以寫出狀態(tài)轉(zhuǎn)移情況：

• 選擇i節(jié)點：f[i][k]等于w[i]加上所有子節(jié)點選擇k-1個節(jié)點的最大權(quán)值
• 不選擇i節(jié)點：f[i][k] = 0

不選擇i節(jié)點很好處理，那么我們?nèi)绾翁幚磉x擇i節(jié)點時，子節(jié)點的情況？

根據(jù)題目描述，我們知道給定的節(jié)點i可能有多個兒子節(jié)點，不妨假設(shè)其有m個兒子節(jié)點。

則可以表示為，在m個兒子上一共選擇k-1個節(jié)點，使得選擇的節(jié)點權(quán)值之和最大。

舉個例子，比如樣例：

我們在計算f[1][4]時，需要考慮對于以2,3,4分別為根節(jié)點子樹，一共選擇3個節(jié)點，來使得權(quán)值最大。也就是說在2子樹中選擇x個節(jié)點，3子樹中選擇y個節(jié)點，4子樹中選擇z個節(jié)點，使得x+y+z=3。

很顯然，該問題同樣是一個動態(tài)規(guī)劃問題：

建立狀態(tài)g[i][j]，g[i][j]表示前i個兒子選擇j個節(jié)點時最大權(quán)值，則有狀態(tài)轉(zhuǎn)移過程：

g[i][j] = max{g[i - 1][j - k] + f[childId][k] | k = 0 .. j}

因此我們可以得到整個動態(tài)規(guī)劃的過程：

// 初始化f數(shù)組 f[][] = -1;dp(root, k):If (k == 0) ThenReturn 0;End IfIf (f[root][k] != -1) Then// 由于可能多次調(diào)用dp(root,k)// 所以這里采用了記憶化的思想Return f[root][k];End If// 不選擇該節(jié)點f[root][k] = 0;// 選擇該節(jié)點g[][] = 0; // 初始化g數(shù)組，需要注意g為該函數(shù)的局部變量For i = 1 .. m // 枚舉子節(jié)點For j = 0 .. k - 1For t = 0 .. jIf g[i][j] < dp(child[i], t) + g[i-1][j-t] Theng[i][j] = dp(child[i], t) + g[i-1][j-t];End IfEnd ForEnd ForEnd ForIf (f[root][k] < g[m][k-1] + w[root]) Thenf[root][k] = g[m][k-1] + w[root];End IfReturn f[root][k];

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 110; int n,m,cnt,f[maxn][maxn]; int score[maxn],pre[maxn]; struct Edge {int key,next; }edge[maxn<<1];void addedge(int x,int y) {edge[cnt].key = y;edge[cnt].next = pre[x];pre[x] = cnt++; }void dfsDP(int cur,int p,int M) {if(M == 0){f[cur][M] = 0;return;}if(f[cur][M] != -1) return;int num = 0,g[maxn][maxn] = {0};for(int i = pre[cur]; i != -1; i = edge[i].next){int v = edge[i].key;if(v == p) continue;num++;for(int j = 0; j < M; j++)for(int t = 0; t <= j; t++){dfsDP(v,cur,t);if(g[num][j] < f[v][t] + g[num-1][j-t])g[num][j] = f[v][t] + g[num-1][j-t];}}if(f[cur][M] < g[num][M-1] + score[cur])f[cur][M] = g[num][M-1] + score[cur]; }int main() { while(scanf("%d%d",&n,&m)!=EOF){for(int i = 1; i <= n; i++)scanf("%d",&score[i]);memset(f,-1,sizeof(f));memset(pre,-1,sizeof(pre));cnt = 0;for(int i = 1; i < n; i++){int a,b;scanf("%d%d",&a,&b);addedge(a,b);addedge(b,a);}dfsDP(1,0,m);printf("%d\n",f[1][m]);}return 0; }

總結(jié)

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

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