資源描述：
《淺談樹的動態(tài)規(guī)劃》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、淺談樹的動態(tài)規(guī)劃樹，是一種很特殊的數(shù)據(jù)結(jié)構(gòu)，關(guān)于它的題目十分的多，兒乎在大部分的比賽當(dāng)中都會出現(xiàn)這類型的題冃，而口研究樹的題冃也是十分有趣的。由于以樹為背景，題H會很明顯地滲透了樹的特征，而樹的特征也正是我們解決這類問題的突破UO樹的問題往往會有一個十分突出的特點：數(shù)據(jù)量十分大。由于樹是十分特殊的圖：連通圖，n個頂點，ml條邊。因此在空間町以承受的范圍內(nèi)n可以達到很大。而且樹的特殊結(jié)構(gòu)也決定了算法的優(yōu)越性。正因為樹的特殊，通常能夠找到十分高效的算法(比如說是0(n))。于是我們解決這類題目的時候應(yīng)
2、當(dāng)牢牢抓住樹的特征，認真分析問題，這樣就能比較好地解決題目了。下面舉一些例子談?wù)剺涞膭討B(tài)規(guī)劃。樹的動態(tài)規(guī)劃，顧名思義，就是在樹上面進行動態(tài)規(guī)劃。樹的動態(tài)規(guī)劃很有特點，雖說對某個結(jié)點來說，狀態(tài)轉(zhuǎn)移的復(fù)雜度是不確定的(這取決于與它相連的邊數(shù))，但是總體來說，每條邊通常只會對應(yīng)常數(shù)次狀態(tài)轉(zhuǎn)移，所以總的復(fù)雜度是0(n)的，這就使樹的動態(tài)規(guī)劃十分高效。例如下面這道題目：『例1』ComputerNetworkAschoolboughtthefirstcomputersometimeago.Duringther
3、ecentyearstheschoolboughtN~1newcomputers.Eachnewcomputerwasconnectedtooneofsettledearlier.Managersofschoolareanxiousabouts1owfunctioningofthenetandwanttoknowforeachcomputernumberSi-maximumdistance,forwhichi-thcomputerneedstosendsignal(i.e.lengthofcabl
4、etothemostdistantcomputer).Youneedtoprovidethisinformalion.InputThereisnaturalnumberN(N<=10000)inthefirstlineofinput,foilowedby(N~l)lineswithdescriptionsofcomputers?i-thlinecontainstwonaturalnumbers-numberofcomputer,towhichi~thcomputerisconnecledandle
5、ngthofcableusedforconneelion.Totallengthofcabledoesnotexceed109.Numbersinlinesofinputareseparatedbyaspace?OutputWriteNlinesinoutputfile.i-thlinemustcontainnumberSifori-thcomputer(l<=i<=N).Sampletest(s)Input31112Output233題目的意思是說：一間學(xué)校前幾年時間買進了第一臺電腦。這幾年又陸
6、續(xù)買TN-1臺電腦。后面買的電腦都與先前買的某一臺電腦用網(wǎng)線連接起來?，F(xiàn)在我們知道后面的N-1臺電腦分別與哪臺電腦連接以及相應(yīng)的網(wǎng)線的長度，任務(wù)是對每一臺電腦K都求出，在另外的N-1臺電腦中，離K最遠的那臺電腦與K的距離（即它們Z間的網(wǎng)線的總長度）。這也是一道關(guān)于樹的題目，而月?和例1十分相似，也是符合動態(tài)規(guī)劃的耍求的。我們也可以類似地先任意選擇一個結(jié)點作為樹的根把樹轉(zhuǎn)為有根樹，然后用動態(tài)規(guī)劃對每個結(jié)點K都求出以結(jié)點K為根的子樹的深度。然而我們同樣碰到了上面的問題，就是K的父親A也會連出去一棵樹，
7、它在原來的無根樹中同樣也屬于K的了樹（即K的“上方了樹”）。但是，現(xiàn)在我們要求的是樹的深度，就不像上題求結(jié)點數(shù)那樣這么容易求了。如呆我們?nèi)匀挥脛討B(tài)規(guī)劃，從A的子樹（除去K這一棵）中選出深度最深的，然后將它的深度加上AK的長作為“上方子樹”的深度，就有可能出現(xiàn)下面這種情況：對于A的每一個兒子K,都要求K的“上方子樹”，而每一次我們都必須求A的所有子樹（除去K的那一?棵）中深度最大的那一棵。這樣的話時間復(fù)朵度就變?yōu)?（n2）了，顯然是十分不優(yōu)的。為了解決這個問題，我們在前面那個過程中，求A的所有子樹的
8、深度的時候，可以順便求出A的了樹中深度最大的兩棵，并記錄是哪兩棵。在以后求K的“上方子樹”時，就能判斷一下，K是不是它父親A的最深的子樹。如果不是，那么A的最深的子樹的深度加上AK的長度就是K的“上方子樹”的深度；否則A的第二深的子樹的深度加上AK的長度就是K的“上方子樹”的深度。這樣就能夠用0（n）的復(fù)雜度求岀所有結(jié)點的“上方子樹”的深度了。解決了這些問題后我們就能直接進行輸出了。（程序請參見附錄）在2003年的全國賽中也冇一道十分類似的題目：『例2』數(shù)據(jù)生成器【題目背景】小明在
