演算法 日更 第九期 樹型動態規劃詳解 二叉蘋果樹

2022-11-24 17:31:59 字數 3314 閱讀 6873

▎前置技能:動態規劃&樹

樹型動態規劃一聽就知道是在樹結構上使用的動態規劃,那麼不會樹結構和動態規劃怎麼行?戳這裡瞭解動態規劃和樹。

▎什麼是樹型動態規劃?

☞『定義』

猜你也不願意看,簡單說就是摻了樹的動態規劃唄,也特別不到**去,只要樹結構掌握的不錯就行了。

☞『為什麼有樹型動態規劃,而沒聽說過圖型動態規劃、佇列型動態規劃什麼的呢?』

這個很容易理解,因為樹這個資料結構很特殊,只有一個前驅,有多個後繼,本就是一個純天然的遞迴結構,而動態規劃常用什麼方法呢?陣列遞推和記憶化搜尋,巧了!記憶化搜尋正是遞迴的方式,這同時也暗示著一件事:樹型動態規劃是不能使用陣列遞推的!要用記憶化搜尋。

☞『樹型動態規劃的方向』

①由葉到根:也就是從葉子結點(遞迴邊界)向根節點(原問題)不斷返回,最終在根節點(原問題)處得到答案。這種樹型動態規劃的方向很常見,也是我們平時使用遞迴時的方式。

②由根到葉:這種題目很不常見,主要就是將所有點當做一次根節點進行求值,然後有父節點向子節點轉移資訊。

☞『樹型動態規劃的順序』

樹型動態規劃可以理解為後序遍歷,也就是先處理好子節點,再返回處理父節點。

▎樹型動態規劃的解題技巧

☞『樹型動態規劃的一般步驟』

①建樹:樹型動態規劃叫個這名字,總得有樹吧,所以,一定要先建樹,建樹時要注意恰當的儲存方式,資料規模較小時使用鄰接矩陣,較大時使用鄰接表,至於指標大佬就請默默走開。

②設計狀態:動態規劃怎麼也得有狀態了吧,一般樹型動態規劃通常是1~2維,所以時間複雜度一般不高,不過只有狀態設計好了,才能正常的進行後續流程。

③狀態轉移方程:這是令人最討厭的東西,純找規律,要找到父節點和子節點之間的關係,才能寫出來。

④確定答案:有些題目的答案需要推理一下,不過很多不需要,這也和狀態的設計有關。

☞『怎麼判斷題目是否適用於樹型動態規劃』

①長得就是樹型動態規劃題,比如後面的二叉蘋果樹那道題;

②先判斷是否是動態規劃,是否符合動態規劃的三大性質;

③是否需要樹;

▎實戰演練

提起一棵蘋果樹,你會想到什麼?

砸到牛頓頭上的那個蘋果?

被喬布斯啃了一口的蘋果?

這可蘋果樹上可不一般,這是我見過的最奇葩的樹。

廢話不多說,直接上題:

時間限制: 1000 ms         記憶體限制: 524288 kb

提交數: 175     通過數: 104 

有一棵二叉蘋果樹,如果數字有分叉,一定是分兩叉,即沒有隻有一個兒子的節點。這棵樹共 n

'>n

個節點,標號 1

'>1

至 n'>

n,樹根編號一定為 1

'>

1。我們用一根樹枝兩端連線的節點編號描述一根樹枝的位置。一棵有四根樹枝的蘋果樹,因為樹枝太多了,需要剪枝。但是一些樹枝上長有蘋果,給定需要保留的樹枝數量,求最多能留住多少蘋果。

第一行兩個數 n

'>

n 和 q

'>

q ,n

'>

n 表示樹的節點數,q

'>

q 表示要保留的樹枝數量。

接下來 n−1

'>

n−1 行描述樹枝資訊,每行三個整數,前兩個是它連線的節點的編號,第三個數是這根樹枝上蘋果數量。

輸出僅一行,表示最多能留住的蘋果的數量。

5 2

1 3 1

1 4 10

2 3 20

3 5 20

21
對於 100% 的資料,1≤q

≤n≤100,n

≠1'>

1≤q≤n≤100,n≠1,每根樹枝上蘋果不超過 30000

'>

30000 個。

無這道題一看就知道是樹型動態規劃,因為這分明就是一道樹型動態規劃題,那麼怎麼做呢?

part one 建樹

假設每行輸入分別對應的變數是a,b,c。

先來考慮建樹,建樹都是應該遞迴建的,請看一下別人部落格,一般都是這樣的。小編的建樹方式不太一樣,那就是一直判斷,如果b沒有父節點,那麼那麼b就是a的子節點,存起來;如果b有父節點,那麼a就是b的子節點,存起來。

那麼左右子樹呢?順序沒有任何關係,所以先存左子樹,後存右子樹,**比較簡單,就不過多解釋了:

1 cin>>n>>q;

2for(int i=1;i<=n-1;i++)311

else

1219 }

part two 設計狀態

我們是要求以根節點保留q條枝條能保留的最多蘋果數。那麼不妨將f[i][j]表示為以i為根節點保留j條枝條能保留的最多蘋果數。

part three 狀態轉移方程

那麼現在來考慮一件事,我們需要向左右兩邊分一些枝條量,各是k-1和j-k-1個(假設左子樹有k個),為什麼都減一呢?小編在除錯**的過程中發現:如果不減一,那麼左右兩邊都會多分一個枝條,原因是轉移時忘了轉移的節點和原節點間有一個枝條。

1

for(int k=0;k<=j;k++)

2

part four 確定答案

小編可能設計的狀態不太和別人一樣,看見別人的部落格答案和我的不一樣,還有設計三維的,別人的答案:f[1][q+1];小編的答案:f[1][q]。

part five 一點忠告

猜猜小編是怎麼錯的?小編顯示忘了刪測試**和記憶化,一直以為**有不可告人的錯誤,結果被忘了刪測試**糾結了很長時間。

好了,**如下:

1 #include2

using

namespace

std;

3],n,q,a,b,c;

4int dp(int i,intj)5

13int maxn=-1

,x;14

for(int k=0;k<=j;k++)

1524

return

f[i][j];25}

26int

main()

2738

else

3946

}47 cout<1

,q);

48return0;

49 }