動(dòng)態(tài)規(guī)劃專題：樹型動(dòng)態(tài)規(guī)劃

1、動(dòng)態(tài)規(guī)劃專題（六）：樹型動(dòng)態(tài)規(guī)劃（重慶巴蜀中學(xué)黃新軍）信息學(xué)競(jìng)賽中通常會(huì)出現(xiàn)這樣的問題：給一棵樹，要求以最少的代價(jià)（或取得最大收益） 完成給定的操作。有很多問題都是在樹和最優(yōu)性的基礎(chǔ)上進(jìn)行了擴(kuò)充和加強(qiáng)，從而變成了棘 手的問題。這類問題通常規(guī)模較大，枚舉算法的效率無(wú)法勝任，貪心算法不能得到最優(yōu)解， 因此要用動(dòng)態(tài)規(guī)劃解決。和一般動(dòng)態(tài)規(guī)劃問題一樣，這類問題的解決要考慮如下三步：1、確立狀態(tài)：幾乎所以的問題都要保存以某結(jié)點(diǎn)為根的子樹的情況，但是要根據(jù)具體 問題考慮是否要加維，加幾維，如何加維。2、狀態(tài)轉(zhuǎn)移：狀態(tài)轉(zhuǎn)移的變化比較多，要根據(jù)具體問題具體分析，這也是本文例題分 析的重點(diǎn)。3、算法實(shí)現(xiàn)：由于樹的

2、結(jié)構(gòu)，使用記憶化搜索比較容易實(shí)現(xiàn)。由于模型建立在樹上，即為樹型動(dòng)態(tài)規(guī)劃?！纠}1】二叉蘋果樹【問題描述】有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個(gè)兒子的結(jié)點(diǎn)），這 棵樹共有N個(gè)結(jié)點(diǎn)（葉子點(diǎn)或者樹枝分叉點(diǎn)），編號(hào)為1-N，樹根編號(hào)一定是1。我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號(hào)來描述一根樹枝的位置。下面是一顆有4個(gè)樹枝 的樹：現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長(zhǎng)有蘋果。給定需要保留的樹枝數(shù) 量，求出最多能留住多少蘋果。【文件輸入】第1行2個(gè)數(shù)，N和Q（1v=Qv=N,1vNv=100）。N表示樹的結(jié)點(diǎn)數(shù)，Q表示要保留的樹 枝數(shù)量。接下來N-1行描述樹枝的信息。每行3個(gè)

3、整數(shù)，前兩個(gè)是它連接的結(jié)點(diǎn)的編號(hào)。 第3個(gè)數(shù)是這根樹枝上蘋果的數(shù)量。每根樹枝上的蘋果不超過30000個(gè)?！疚募敵觥枯敵鑫募H一個(gè)數(shù)，表示最多能留住的蘋果的數(shù)量。3【樣例輸入】4 103 205 20【樣例輸出】21【思路點(diǎn)撥】由題意可知，需要保留的樹枝數(shù)量為Q條，即保留結(jié)點(diǎn)t=Q+1個(gè)。樹根必須保留，可 以分三種情況討論保留蘋果的最大數(shù)。樹根的左子樹為空，全部保留右子樹，右子樹中保留t-1個(gè)結(jié)點(diǎn)；樹根的右子樹為空，全部保留左子樹，左子樹中保留t-1個(gè)結(jié)點(diǎn)；樹根的兩棵子樹都為非空，設(shè)左子樹保留k個(gè)結(jié)點(diǎn)，則右子樹保留t-k-1個(gè)結(jié)點(diǎn)。要得到保留樹根時(shí)的蘋果最大數(shù)，只需要求上述三個(gè)方案中的最大值。

4、設(shè)樹根為V，左 兒子為chv,1,右兒子為chv，2，對(duì)于方案，要取得該方案的最大值，需要取得以chv， 2為根，保留t-1個(gè)結(jié)點(diǎn)的最大值。這時(shí)同樣具有上述三種方案。其他情況同理；由此 可以看出，該問題具有明顯的最優(yōu)子結(jié)構(gòu)性質(zhì)，每個(gè)問題都與左右兒子結(jié)點(diǎn)有關(guān)系，但不與 孫子結(jié)點(diǎn)發(fā)生關(guān)系，具備無(wú)后效性；且計(jì)算方案時(shí)，搜索子結(jié)構(gòu)時(shí)具備重疊性，所以可以用 動(dòng)態(tài)規(guī)劃來解決。階段和狀態(tài)：fv，t：表示以v為根的樹上保留t個(gè)節(jié)點(diǎn)的最大權(quán)值和。設(shè)chv，1,chv， 2分別存v節(jié)點(diǎn)的左右孩子。狀態(tài)轉(zhuǎn)移方程：fv,t=maxfchv,1i+fchv,2t-i-1+numv(0=i=t-1)初始化：fv,t=0,

5、(t=0)；fv,t=numv； (chv,1=0 且 chv,2=0)Answer=f1,t；【例題2】加分二叉樹(NOIP2003)【問題描述】設(shè)一棵n個(gè)結(jié)點(diǎn)的二叉樹tree的中序遍歷為(1,2,3,.,n)，其中數(shù)字1,2,3,.,n為結(jié)點(diǎn)編 號(hào)。每個(gè)結(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)(均為正整數(shù))，記第i個(gè)結(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子 樹都有一個(gè)加分，任一棵子樹subtree (也包含tree本身)的加分計(jì)算方法如下：subtree的左子樹的加分xsubtree的右子樹的加分+subtree的根的分?jǐn)?shù)若某個(gè)子樹為空，規(guī)定其加分為1，葉子的加分就是葉結(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空 子樹。試求一棵符

6、合中序遍歷為(1,2,3,.,n)且加分最高的二叉樹tree。要求輸出；tree的最高加分tree的前序遍歷【輸入格式】第1行：一個(gè)整數(shù)n (n30)，為結(jié)點(diǎn)個(gè)數(shù)。第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)結(jié)點(diǎn)的分?jǐn)?shù)(分?jǐn)?shù)100)?！据敵龈袷健康?行：一個(gè)整數(shù)，為最高加分(結(jié)果不會(huì)超過4,000,000,000)。第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?5 7 1 2 10【輸出樣例】145【思路點(diǎn)撥】本題已經(jīng)說明了問題的模型是一棵樹，而且是一棵中序遍歷為1,2,3,.,n的二叉樹。而 對(duì)于一棵中序遍歷為1,2,3,.,n的二叉樹有很多種形式，對(duì)于樣例，下圖就列出了 3種形式，

7、 而按題意，第三種形式得到的得分最大。5(lA)2(5*1+7)*10+2=122(1*10+2)*5+7=67(5+7)*(10+2)+1=145性質(zhì)：中序遍歷是按“左-根-右”方式進(jìn)行遍歷二叉樹，因此二叉樹左孩子遍歷序列一 定在根結(jié)點(diǎn)的左邊，右孩子遍歷序列一定在根結(jié)點(diǎn)的右邊!因此，假設(shè)二叉樹的根結(jié)點(diǎn)為k，那么中序遍歷為1,2,.,n的遍歷序列，左孩子序列為1,2,.,k-1，右孩子序列為k+1,k+2,.,n，如下圖1,k-1kk+1.nII I左孩子根右孩子夕偵孩子k+1.,n左孩子我們思考的方式變?yōu)?，要使得整棵樹最?yōu)，必須左孩子和右孩子都最優(yōu)，因此設(shè)fij 表示以結(jié)點(diǎn)i,i+1,i+2

8、.,j組成的二叉樹所得的最大加分；設(shè)根為k，則枚舉根結(jié)點(diǎn)dk表示 k結(jié)點(diǎn)的最大分值；故有：fi,j=maxfi,k-1*fk+1,j +dk;( 1=i=k=j=n)初始條件：fi,i=dkAnswer=f1,n時(shí)間復(fù)雜度：O(n3)題目還要求輸出最大加分樹的前序遍歷序列，因此要構(gòu)造這個(gè)樹，我們只需記錄每次的 決策值，令pi,j=k，表示中序遍歷為i,i+1,.,j的二叉樹的取最優(yōu)決策時(shí)的根結(jié)點(diǎn)為k，最 后前序遍歷這個(gè)樹即可?！纠}3】選課(CTSC1997)【問題描述】大學(xué)里實(shí)行學(xué)分。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并考核通過就能獲 得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門課的

9、學(xué)分的總和。每個(gè)學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的 基礎(chǔ)知識(shí)，必須在選了其他的一些課程的基礎(chǔ)上才能選修。例如，數(shù)據(jù)結(jié)構(gòu)必須在選修 了高級(jí)語(yǔ)言程序設(shè)計(jì)之后才能選修。我們稱高級(jí)語(yǔ)言程序設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)的先 修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每 門課都有一個(gè)課號(hào)，課號(hào)依次為1,2,3,.。下面舉例說明：課號(hào)先修課號(hào)學(xué)分學(xué)生不可能學(xué)完大學(xué)所開設(shè)的所有課程，因此必須在入學(xué)時(shí)選定自己要學(xué)的課程。每個(gè) 學(xué)生可選課程的總數(shù)是給定的。現(xiàn)在請(qǐng)你找出一種選課方案，使得你能得到學(xué)分最多，并且 必須滿足先修課優(yōu)先的原則。假定課程之間不存在時(shí)

10、間上的沖突?！疚募斎搿枯斎胛募牡谝恍邪▋蓚€(gè)正整數(shù)M，N(中間用一個(gè)空格隔開)，其中M表示待選課程 總數(shù)(1=M=1000)，N表示學(xué)生可以選的課程總數(shù)(1=Nnm;for(i=1;ikv;ai.value=v;if(sonk=0)ak.left=i;else asonk.right=i;sonk=i;(2)樹上的動(dòng)態(tài)規(guī)劃創(chuàng)建。以結(jié)點(diǎn)i為階段，以選的課程數(shù)j為狀態(tài)，以到達(dá)葉子結(jié) 點(diǎn)為邊界，以每個(gè)結(jié)點(diǎn)能取得的最高得分為決策，在整棵樹上的決策構(gòu)成一個(gè)決策序列。用 fij表示結(jié)點(diǎn)i為根的子樹中取j門課程的最高得分，對(duì)樹型結(jié)構(gòu)分2種情況進(jìn)行動(dòng)態(tài)規(guī)劃 設(shè)計(jì)。由于是普通有序樹或森林轉(zhuǎn)換成的二叉樹，所以

11、需要對(duì)右子樹進(jìn)行特殊處理。當(dāng)只有 右子樹時(shí)，此時(shí)i結(jié)點(diǎn)不能選，只能選擇i結(jié)點(diǎn)的右子樹，即選擇課程數(shù)為j。所以此時(shí)的 狀態(tài)轉(zhuǎn)移方程為：fij=fi.r,j。由于要選擇左子樹時(shí)，樹根必須選擇，所以可以把只有左子樹和左右子樹都有兩種合 并起來進(jìn)行考慮，得到動(dòng)態(tài)規(guī)劃方程為：fij=maxfi.lk+fi.rj-k-1+ai(0=kx且y的約數(shù)和為x，那么x也可以變成y。例如，4可以變?yōu)?，1可 以變?yōu)?。限定所有的數(shù)字變換在不超過n的正整數(shù)范圍內(nèi)進(jìn)行，求不斷進(jìn)行數(shù)字變換且沒 有重復(fù)數(shù)字出現(xiàn)的最多變換步數(shù)。【文件輸入】輸入一個(gè)正整數(shù)n【文件輸出】輸出不斷進(jìn)行數(shù)字變換且沒有重復(fù)數(shù)字出現(xiàn)的最多變換步數(shù)?！緲?/p>

12、例輸入】7【樣例輸出】3【樣例說明】一種方案為：4317?！緮?shù)據(jù)范圍】nd1i，則 d2i=d1i; d1i=d1j+1;否則，若 d1j+1d2i，則 d2i=d1j+1;最后掃描所有的結(jié)點(diǎn)，找最大的d1i+d2i的值?！纠}5】戰(zhàn)略游戲【問題描述】Bob喜歡玩電腦游戲，特別是戰(zhàn)略游戲。但是他經(jīng)常無(wú)法找到快速玩過游戲的辦法?，F(xiàn) 在他有個(gè)問題。他要建立一個(gè)古城堡，城堡中的路形成一棵樹。他要在這棵樹的結(jié)點(diǎn)上放置最少數(shù)目的 士兵，使得這些士兵能瞭望到所有的路。注意：某個(gè)士兵在一個(gè)結(jié)點(diǎn)上時(shí)，與該結(jié)點(diǎn)相連的所有邊將都可以被瞭望到。請(qǐng)你編一程序，給定一樹，幫Bob計(jì)算出他需要放置最少的士兵?！疚募斎搿?/p>

13、輸入文件中數(shù)據(jù)表示一棵樹，描述如下：第一行N，表示樹中結(jié)點(diǎn)的數(shù)目。第二行至第N+1行，每行描述每個(gè)結(jié)點(diǎn)信息，依次為：該結(jié)點(diǎn)標(biāo)號(hào)i，k(后面有k條邊 與結(jié)點(diǎn)I相連)，接下來k個(gè)數(shù)，分別是每條邊的另一個(gè)結(jié)點(diǎn)標(biāo)號(hào)r1，r2, .，rk。對(duì)于一個(gè)n(0n=1500)個(gè)結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號(hào)在0到n-1之間，在輸入文件中每條邊只 出現(xiàn)一次。【文件輸出】輸出文件僅包含一個(gè)數(shù)，為所求的最少的士兵數(shù)目?！緲永斎搿?0 1 1 TOC o 1-5 h z HYPERLINK l bookmark140 o Current Document 2 2 30 HYPERLINK l bookmark109 o Curr

14、ent Document 0【樣例輸出】1【思路點(diǎn)撥】按照要求構(gòu)建一張關(guān)系圖，可見這是一棵樹。對(duì)于這類最值問題，向來是用動(dòng)態(tài)規(guī)劃求解的。任何一個(gè)點(diǎn)的取舍可以看作一種決策，設(shè)fi,1表示i點(diǎn)放士兵時(shí)，以i為根的子樹需要 的最少士兵數(shù)目；fi,0表示i點(diǎn)不放士兵時(shí)，以i為根的子樹需要的最少士兵數(shù)目。當(dāng)點(diǎn)i不放時(shí)，則它的所有兒子都必須放，即fi,0=fi,0+fj,1；其中j為i的兒子。當(dāng)點(diǎn)i放時(shí)，則它的所有兒子放與不放無(wú)所謂，但應(yīng)該取兩種情況的最大值。即fi,1=fi,1+max(fj,1,fj,0)；其中 j 為 i 的兒子。初始條件：fi,0=0;fi,1=1【例題6】皇宮看守【問題描述】太平

15、王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)?；蕦m以午門為起點(diǎn)，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望 見。大內(nèi)保衛(wèi)森嚴(yán)，三步一崗，五步一哨，每個(gè)宮殿都要有人全天候看守，在不同的宮殿安 排看守所需的費(fèi)用不同。可是陸小鳳手上的經(jīng)費(fèi)不足，無(wú)論如何也沒法在每個(gè)宮殿都安置留守侍衛(wèi)。編程任務(wù)：幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費(fèi)的經(jīng)費(fèi)最少?！疚募斎搿枯斎胛募袛?shù)據(jù)表示一棵樹，描述如下：第1行n，表示樹中結(jié)點(diǎn)的數(shù)目。第2行至第n+1行，每行描述每個(gè)宮殿結(jié)點(diǎn)信息，依次為：該宮殿結(jié)點(diǎn)標(biāo)號(hào)i(0i=n), 在該宮殿安置侍衛(wèi)所需的經(jīng)費(fèi)k,該邊的兒子數(shù)m,接下來m個(gè)數(shù)，分別是

16、這個(gè)節(jié)點(diǎn)的m個(gè)兒 子的標(biāo)號(hào) r1,r2,.,rm。對(duì)于一個(gè)n(0n=1500)個(gè)結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號(hào)在1到n之間，且標(biāo)號(hào)不重復(fù)?！疚募敵觥枯敵鑫募H包含一個(gè)數(shù)，為所求的最少的經(jīng)費(fèi)?！緲永斎搿?1 30 3 2 3 42 16 2 5 65*115 11 0【樣例輸出】25【分析樣例】該圖有6個(gè)區(qū)域如圖1,安排情況如圖2,紅色點(diǎn)為安排了警衛(wèi)。2號(hào)警衛(wèi)可以觀察1, 2, 5, 6； 3號(hào)警衛(wèi)可以觀察1, 3； 4號(hào)警衛(wèi)可以觀察1, 4； 費(fèi)用：16+5+4=25【試題分析】本題已知模型是一棵樹，因此我們?cè)囍脴湫蝿?dòng)態(tài)規(guī)劃來解決。對(duì)于本題，每個(gè)安全結(jié) 點(diǎn)i,都有3種狀態(tài)分別為：要么在父親結(jié)點(diǎn)安排警

17、衛(wèi)，即被父親看到要么在兒子結(jié)點(diǎn)安排警衛(wèi)，即被兒子看到要么安排警衛(wèi)設(shè)f(i,0)表示i結(jié)點(diǎn)被父親看時(shí)，以i為根的子樹需要安排的最少士兵; f(i,1)表示i被它的兒子看時(shí)，以i為根的子樹需要安排的最少士兵; f(i,2)表示在i安排警衛(wèi)時(shí)，以i為根的子樹需要安排的最少士兵；父親結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)i l兒子結(jié)點(diǎn)4現(xiàn)在只需針對(duì)這三種狀態(tài)，設(shè)計(jì)出狀態(tài)轉(zhuǎn)移方程。對(duì)于f(i,0)，表示i被父親看到，這時(shí)i沒有安排警衛(wèi)，i的兒子要么安排警衛(wèi)，要 么被它的后代看到，所以有：f /,0=的 mnf g ,1, f i.k ,2k=1對(duì)于f(i,1),表示i被兒子看到，即i的某個(gè)兒子安排了警衛(wèi)，其他兒子需要安排警 衛(wèi)或者被它的后代看到，所以有：f i,1 = i 的云 3inf i.k ,1, f ik ,2 + dk=1其中 d = minf i.k ,2 - minf i.k ,1, f i.k ,2對(duì)于f(i,2),表示i安排了警衛(wèi)，i的兒子可以安排警衛(wèi)，也可以被i的兒子的兒子 看守，還可以被父親看守，所以有：f i,2= 的尤ILinf i.k ,0, f i.k ,1