動(dòng)態(tài)規(guī)劃專(zhuān)題：樹(shù)型動(dòng)態(tài)規(guī)劃

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

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

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

4、設(shè)樹(shù)根為V，左 兒子為chv,1,右兒子為chv，2，對(duì)于方案，要取得該方案的最大值，需要取得以chv， 2為根，保留t-1個(gè)結(jié)點(diǎn)的最大值。這時(shí)同樣具有上述三種方案。其他情況同理；由此 可以看出，該問(wèn)題具有明顯的最優(yōu)子結(jié)構(gòu)性質(zhì)，每個(gè)問(wèn)題都與左右兒子結(jié)點(diǎn)有關(guān)系，但不與 孫子結(jié)點(diǎn)發(fā)生關(guān)系，具備無(wú)后效性；且計(jì)算方案時(shí)，搜索子結(jié)構(gòu)時(shí)具備重疊性，所以可以用 動(dòng)態(tài)規(guī)劃來(lái)解決。階段和狀態(tài)：fv，t：表示以v為根的樹(shù)上保留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】加分二叉樹(shù)(NOIP2003)【問(wèn)題描述】設(shè)一棵n個(gè)結(jié)點(diǎn)的二叉樹(shù)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è)子 樹(shù)都有一個(gè)加分，任一棵子樹(shù)subtree (也包含tree本身)的加分計(jì)算方法如下：subtree的左子樹(shù)的加分xsubtree的右子樹(shù)的加分+subtree的根的分?jǐn)?shù)若某個(gè)子樹(shù)為空，規(guī)定其加分為1，葉子的加分就是葉結(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空 子樹(shù)。試求一棵符

6、合中序遍歷為(1,2,3,.,n)且加分最高的二叉樹(shù)tree。要求輸出；tree的最高加分tree的前序遍歷【輸入格式】第1行：一個(gè)整數(shù)n (n30)，為結(jié)點(diǎn)個(gè)數(shù)。第2行：n個(gè)用空格隔開(kāi)的整數(shù)，為每個(gè)結(jié)點(diǎn)的分?jǐn)?shù)(分?jǐn)?shù)100)。【輸出格式】第1行：一個(gè)整數(shù)，為最高加分(結(jié)果不會(huì)超過(guò)4,000,000,000)。第2行：n個(gè)用空格隔開(kāi)的整數(shù)，為該樹(shù)的前序遍歷?！据斎霕永?5 7 1 2 10【輸出樣例】145【思路點(diǎn)撥】本題已經(jīng)說(shuō)明了問(wèn)題的模型是一棵樹(shù)，而且是一棵中序遍歷為1,2,3,.,n的二叉樹(shù)。而 對(duì)于一棵中序遍歷為1,2,3,.,n的二叉樹(shù)有很多種形式，對(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)行遍歷二叉樹(shù)，因此二叉樹(shù)左孩子遍歷序列一 定在根結(jié)點(diǎn)的左邊，右孩子遍歷序列一定在根結(jié)點(diǎn)的右邊!因此，假設(shè)二叉樹(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)?，要使得整棵?shù)最優(yōu)，必須左孩子和右孩子都最優(yōu)，因此設(shè)fij 表示以結(jié)點(diǎn)i,i+1,i+2

8、.,j組成的二叉樹(shù)所得的最大加分；設(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)題目還要求輸出最大加分樹(shù)的前序遍歷序列，因此要構(gòu)造這個(gè)樹(shù)，我們只需記錄每次的 決策值，令pi,j=k，表示中序遍歷為i,i+1,.,j的二叉樹(shù)的取最優(yōu)決策時(shí)的根結(jié)點(diǎn)為k，最 后前序遍歷這個(gè)樹(shù)即可?！纠}3】選課(CTSC1997)【問(wèn)題描述】大學(xué)里實(shí)行學(xué)分。每門(mén)課程都有一定的學(xué)分，學(xué)生只要選修了這門(mén)課并考核通過(guò)就能獲 得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門(mén)課的

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

10、間上的沖突。【文件輸入】輸入文件的第一行包括兩個(gè)正整數(shù)M，N(中間用一個(gè)空格隔開(kāi))，其中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)樹(shù)上的動(dòng)態(tài)規(guī)劃創(chuàng)建。以結(jié)點(diǎn)i為階段，以選的課程數(shù)j為狀態(tài)，以到達(dá)葉子結(jié) 點(diǎn)為邊界，以每個(gè)結(jié)點(diǎn)能取得的最高得分為決策，在整棵樹(shù)上的決策構(gòu)成一個(gè)決策序列。用 fij表示結(jié)點(diǎn)i為根的子樹(shù)中取j門(mén)課程的最高得分，對(duì)樹(shù)型結(jié)構(gòu)分2種情況進(jìn)行動(dòng)態(tài)規(guī)劃 設(shè)計(jì)。由于是普通有序樹(shù)或森林轉(zhuǎn)換成的二叉樹(shù)，所以

11、需要對(duì)右子樹(shù)進(jìn)行特殊處理。當(dāng)只有 右子樹(shù)時(shí)，此時(shí)i結(jié)點(diǎn)不能選，只能選擇i結(jié)點(diǎn)的右子樹(shù)，即選擇課程數(shù)為j。所以此時(shí)的 狀態(tài)轉(zhuǎn)移方程為：fij=fi.r,j。由于要選擇左子樹(shù)時(shí)，樹(shù)根必須選擇，所以可以把只有左子樹(shù)和左右子樹(shù)都有兩種合 并起來(lái)進(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ù)字變換在不超過(guò)n的正整數(shù)范圍內(nèi)進(jìn)行，求不斷進(jìn)行數(shù)字變換且沒(méi) 有重復(fù)數(shù)字出現(xiàn)的最多變換步數(shù)?！疚募斎搿枯斎胍粋€(gè)正整數(shù)n【文件輸出】輸出不斷進(jìn)行數(shù)字變換且沒(méi)有重復(fù)數(shù)字出現(xiàn)的最多變換步數(shù)?！緲?/p>

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

13、輸入文件中數(shù)據(jù)表示一棵樹(shù)，描述如下：第一行N，表示樹(shù)中結(jié)點(diǎn)的數(shù)目。第二行至第N+1行，每行描述每個(gè)結(jié)點(diǎn)信息，依次為：該結(jié)點(diǎn)標(biāo)號(hào)i，k(后面有k條邊 與結(jié)點(diǎn)I相連)，接下來(lái)k個(gè)數(shù)，分別是每條邊的另一個(gè)結(jié)點(diǎn)標(biāo)號(hào)r1，r2, .，rk。對(duì)于一個(gè)n(0n=1500)個(gè)結(jié)點(diǎn)的樹(shù)，結(jié)點(diǎn)標(biāo)號(hào)在0到n-1之間，在輸入文件中每條邊只 出現(xiàn)一次。【文件輸出】輸出文件僅包含一個(gè)數(shù)，為所求的最少的士兵數(shù)目。【樣例輸入】40 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)系圖，可見(jiàn)這是一棵樹(shù)。對(duì)于這類(lèi)最值問(wèn)題，向來(lái)是用動(dòng)態(tài)規(guī)劃求解的。任何一個(gè)點(diǎn)的取舍可以看作一種決策，設(shè)fi,1表示i點(diǎn)放士兵時(shí)，以i為根的子樹(shù)需要 的最少士兵數(shù)目；fi,0表示i點(diǎn)不放士兵時(shí)，以i為根的子樹(shù)需要的最少士兵數(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】皇宮看守【問(wèn)題描述】太平

15、王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)。皇宮以午門(mén)為起點(diǎn)，直到后宮嬪妃們的寢宮，呈一棵樹(shù)的形狀；某些宮殿間可以互相望 見(jiàn)。大內(nèi)保衛(wèi)森嚴(yán)，三步一崗，五步一哨，每個(gè)宮殿都要有人全天候看守，在不同的宮殿安 排看守所需的費(fèi)用不同。可是陸小鳳手上的經(jīng)費(fèi)不足，無(wú)論如何也沒(méi)法在每個(gè)宮殿都安置留守侍衛(wèi)。編程任務(wù)：幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費(fèi)的經(jīng)費(fèi)最少?！疚募斎搿枯斎胛募袛?shù)據(jù)表示一棵樹(shù)，描述如下：第1行n，表示樹(shù)中結(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,接下來(lái)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)的樹(shù)，結(jié)點(diǎn)標(biāo)號(hào)在1到n之間，且標(biāo)號(hào)不重復(fù)?！疚募敵觥枯敵鑫募H包含一個(gè)數(shù)，為所求的最少的經(jīng)費(fèi)。【樣例輸入】61 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【試題分析】本題已知模型是一棵樹(shù)，因此我們?cè)囍脴?shù)形動(dòng)態(tài)規(guī)劃來(lái)解決。對(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為根的子樹(shù)需要安排的最少士兵; f(i,1)表示i被它的兒子看時(shí)，以i為根的子樹(shù)需要安排的最少士兵; f(i,2)表示在i安排警衛(wèi)時(shí)，以i為根的子樹(shù)需要安排的最少士兵；父親結(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沒(mé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