資源描述：
《《樹形動(dòng)態(tài)規(guī)劃》PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、樹型動(dòng)態(tài)規(guī)劃JSOI2010冬令營引言樹是一種特殊的圖，可以描述比較復(fù)雜的關(guān)系，而大多數(shù)動(dòng)歸都是在一維二維這種規(guī)則的背景下的，再加上樹遞歸定義的性質(zhì)，可以說是一種非常合適的動(dòng)歸框架，樹型動(dòng)態(tài)規(guī)劃就成為動(dòng)規(guī)中重要的一類題型。因?yàn)闃淇梢悦枋霰容^復(fù)雜的關(guān)系，這對選手分析問題的能力有較高的要求，在尋找最優(yōu)子結(jié)構(gòu)、組織狀態(tài)時(shí)往往需要?jiǎng)?chuàng)造性思維，而且樹型動(dòng)態(tài)規(guī)劃對數(shù)學(xué)要求不高，一般不涉及單調(diào)性優(yōu)化，所以競賽中往往將它作為側(cè)重考察選手分析思考能力的題出現(xiàn)。例一、問題描述給定一棵樹，樹的每個(gè)節(jié)點(diǎn)有一個(gè)權(quán)值，要求從中選出一些不相鄰的點(diǎn)，使選出的節(jié)點(diǎn)
2、權(quán)值和最大。例一、確定狀態(tài)對于大多數(shù)樹型動(dòng)態(tài)規(guī)劃問題，都是用一棵子樹的根節(jié)點(diǎn)編號(hào)來作為代表這棵子樹的第一維狀態(tài)，然后再根據(jù)需要加維。對于本題：用f[i][0]表示不選i時(shí)，以i為根子樹的最大權(quán)值；用f[i][1]表示選擇i時(shí)，以i為根子樹的最大值。例一、狀態(tài)轉(zhuǎn)移f[i][0]=sum(max(f[j][0],f[j][1]))f[i][1]=sum(f[j][0])例一、狀態(tài)轉(zhuǎn)移因?yàn)闃涞奶厥饨Y(jié)構(gòu)，任何兩個(gè)點(diǎn)只有唯一通路，所以很容易滿足無后效性。假如本題給定的是圖而不是樹，那么顯然就無法用動(dòng)歸解決了。例一、兩種實(shí)現(xiàn)方式記憶劃搜索：易
3、于實(shí)現(xiàn)，但可能會(huì)爆棧拓?fù)渑判颍珓?dòng)歸：實(shí)現(xiàn)起來比較麻煩例一、兩種實(shí)現(xiàn)方式實(shí)現(xiàn)方式的選擇因題而異，對于本題，首先要保證程序不會(huì)出錯(cuò)。但一般來說，在保證正確的前提下，記憶劃搜索更加易于實(shí)現(xiàn)，且在對于復(fù)雜的題目，記憶劃搜索更加直觀，便于思考。例二、問題描述在一棵節(jié)點(diǎn)數(shù)不超過200000的樹中，每條邊都有一個(gè)長度值，現(xiàn)要求在樹中選擇3個(gè)點(diǎn)X、Y、Z，滿足X到Y(jié)的距離不大于X到Z的距離，且X到Y(jié)的距離與Y到Z的距離之和最大，求這個(gè)最大值。例二、問題分析三種情況例二、問題分析
4、XY
5、+
6、YZ
7、
8、XY
9、+
10、YX
11、+
12、XZ
13、例二、問題分析例二、問題
14、分析現(xiàn)在只要考慮這一種情況要滿足
15、Xa
16、＋
17、aY
18、≦
19、Xa
20、+
21、aZ
22、
23、Xa
24、＋2
25、aY
26、＋
27、aZ
28、最大例二、問題分析現(xiàn)在我們考慮分叉點(diǎn)a很明顯，要使目標(biāo)值最大，XYZ必是離a最遠(yuǎn)的三點(diǎn)，且在以a為根的三棵不同子樹中。Y就是三點(diǎn)中離a第二遠(yuǎn)的點(diǎn)。顯然，三個(gè)點(diǎn)要么位于以a為根的子樹中，要么位于以a為根的子樹外。例二、問題分析求在子樹中的三個(gè)最遠(yuǎn)點(diǎn)，方法很簡單。在兒子已經(jīng)算好的情況下，父節(jié)點(diǎn)只要保留其中最遠(yuǎn)點(diǎn)最遠(yuǎn)的三個(gè)兒子的最遠(yuǎn)點(diǎn)即可。子樹外的最遠(yuǎn)點(diǎn)如何求？例二、問題分析把這棵樹再遍歷一遍，進(jìn)行一次BFS，深度小的先訪問，深度大的后訪
29、問，就保證了訪問到某一個(gè)節(jié)點(diǎn)的時(shí)候，其父親節(jié)點(diǎn)已經(jīng)被訪問過了。此次遍歷時(shí)，對于點(diǎn)a，檢查其父親節(jié)點(diǎn)，只需求出到其父親節(jié)點(diǎn)的最遠(yuǎn)的，且不在以a為根的子樹中的那點(diǎn)即可。例三、問題描述有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個(gè)兒子的結(jié)點(diǎn)）。 這棵樹共有N（1<=N<=100）個(gè)結(jié)點(diǎn)（葉子點(diǎn)或者樹枝分叉點(diǎn)），編號(hào)為1-N,樹根編號(hào)一定是1?，F(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。給定需要保留的樹枝數(shù)量P，求出最多能留住多少蘋果。例三、問題分析這題的權(quán)值在邊上，這在思考時(shí)有些別扭，其實(shí)只要把邊的權(quán)值轉(zhuǎn)移到
30、兒子節(jié)點(diǎn)上，問題性質(zhì)不變。這樣狀態(tài)就應(yīng)該容易想到了，f[i][j]表示以i節(jié)點(diǎn)為根的子樹保留j個(gè)節(jié)點(diǎn)所得的最大值。因?yàn)楦?jié)點(diǎn)沒有權(quán)值，所以我們要保留p+1個(gè)點(diǎn)。例三、狀態(tài)轉(zhuǎn)移f[i][j]＝max｛f[i_left][k]+f[i_right][j-1-k]｝(0<=k<=j-1)邊界f[i][0]＝0；f[i][1]=value[i]最后f[1][p+1]就是答案例四、問題描述學(xué)校開設(shè)了N（N<300）門的選修課程，每個(gè)學(xué)生可選課程的數(shù)量M是給定的。學(xué)生選修了這M門課并考核通過就能獲得相應(yīng)的學(xué)分。在選修課程中，有些課程可以直接選
31、修，有些課程有一門直接的先修課。你的任務(wù)是為自己確定一個(gè)選課方案，使得你能得到的學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時(shí)間上的沖突。例四、問題分析由于每門課至多只有一門直接先修課，我們把沒有先修課的課強(qiáng)制規(guī)定一門空的先修課，這樣所有課就構(gòu)成了一棵樹。現(xiàn)在就是要從中選出m＋1門課，被選擇的課必須滿足其所有祖先都被選擇。例四、問題分析這樣看來這題和上題差不多：從根開始，把m＋1個(gè)機(jī)會(huì)分配下去。狀態(tài)也很容易想到，f[i][k]表示以i為根的子樹中選k門課的最大學(xué)分。但是這題的樹不是二叉的，這就不能用上題的方法分配附加
32、維了。例四、問題分析假設(shè)某個(gè)節(jié)點(diǎn)的所有孩子的狀態(tài)值都已經(jīng)計(jì)算出來了，現(xiàn)在要據(jù)此計(jì)算出該節(jié)點(diǎn)所有狀態(tài)值。對于某一孩子i，可以視為一個(gè)沒有固定的費(fèi)用和價(jià)值，它的價(jià)值隨著分配給它的費(fèi)用而變化的物品。這就是一類經(jīng)典的背包問題了，每次利用計(jì)算好的兒子求父親的
