1、樹型動態(tài)規(guī)劃,朱全民 ,加分二叉樹,設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點編號。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)），記第j個節(jié)點的分?jǐn)?shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下： subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分?jǐn)?shù) 若某個子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。不考慮它的空。 子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷

2、,例一 加分二叉樹,【輸入格式】 第1行：一個整數(shù)n（n30），為節(jié)點個數(shù)。 第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分?jǐn)?shù)（分?jǐn)?shù)100）。 【輸出格式】 第1行：一個整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。 第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷。 【輸入樣例】 5 5 7 1 2 10 【輸出樣例】 145 3 1 2 4 5,分析,如果整棵樹的權(quán)值最大，必然有左子樹的權(quán)值最大，右子樹德權(quán)值也最大，符合最優(yōu)性原理。,可行算法,我們試著寫出狀態(tài)轉(zhuǎn)移方程： fi,j=maxi=t=j | dt+fi,t-1ft+1,j 初始： f(i,i)=di 目標(biāo)：f(1,n)

3、 這樣，我們可以寫出一個動態(tài)規(guī)劃的算法，可以按照狀態(tài)fi,j中i與j的距離來劃分階段(當(dāng)然也有其它的劃分階段的辦法),先處理掉邊界情況(空樹和只含有一個節(jié)點的樹),然后就可以按照階段自底向上進(jìn)行動態(tài)規(guī)劃了，最后再遞歸地輸出，注意要保存每次決策。 時間復(fù)雜度 O(n3),例二 選課,大學(xué)里實行學(xué)分。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并考核通過就能獲得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門課的學(xué)分的總和。 每個學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如，數(shù)據(jù)結(jié)構(gòu)必須在選修了高級語言程序設(shè)計之后才能選修

4、。我們稱高級語言程序設(shè)計是數(shù)據(jù)結(jié)構(gòu)的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每門課都有一個課號，課號依次為1，2，3，。,選課,下面舉例說明 上例中1是2的先修課，即如果要選修2，則1必定已被選過。同樣，如果要選修3，那么1和2都一定已被選修過。 學(xué)生不可能學(xué)完大學(xué)所開設(shè)的所有課程，因此必須在入學(xué)時選定自己要學(xué)的課程。每個學(xué)生可選課程的總數(shù)是給定的?，F(xiàn)在請你找出一種選課方案，使得你能得到學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的沖突。,選課,輸入 輸入文件的第一行包括兩個正整數(shù)M、N（中間用一個空格隔開）其中M表示待選課程總數(shù)（1

5、M1000)，N表示學(xué)生可以選的課程總數(shù)（1NM)。 以下M行每行代表一門課，課號依次為1，2M。每行有兩個數(shù)（用一個空格隔開），第一個數(shù)為這門課的先修課的課號（若不存在先修課則該項為0），第二個數(shù)為這門課的學(xué)分。學(xué)分是不超過10的正整數(shù)。 輸出 輸出文件第一行只有一個數(shù)，即實際所選課程的學(xué)分總數(shù)。以下N行每行有一個數(shù)，表示學(xué)生所選課程的課號。,樣例分析,分析,們可以選取某一個點k的條件只是它的父節(jié)點已經(jīng)被選取或者它自己為根節(jié)點；而且我們不論如(何取k的子孫節(jié)點，都不會影響到它父節(jié)點的選取情況，這滿足無后效性原則。于是我們猜測，是不是可以以節(jié)點為階段，進(jìn)行動態(tài)規(guī)劃呢？ 我們用函數(shù)f(i,j)表

6、示以第i個節(jié)點為父節(jié)點，取j個子節(jié)點的最佳代價，則： 可是如此規(guī)劃，其效率與搜索毫無差別，雖然我們可以再次用動態(tài)規(guī)劃來使它的復(fù)雜度變?yōu)槠椒郊?，但顯得過于麻煩。,改造樹,轉(zhuǎn)變?yōu)槎鏄?。如果兩?jié)點a,b同為兄弟，則將b設(shè)為a的右節(jié)點；如果節(jié)點b是節(jié)點a的兒子，則將節(jié)點b設(shè)為節(jié)點a的左節(jié)點。樹改造完成后如圖3。 我們用函數(shù)f(I,j)表示以第i個節(jié)點為父節(jié)點，取j個子節(jié)點的最佳代價，這和前一個函數(shù)表示的意義是一致的，但方程有了很大的改變：,轉(zhuǎn)化為二叉樹求解,1=i=m,1=j=n,0=kj 這個方程的時間復(fù)雜度最大為n3，十分優(yōu)秀了。 在具體實現(xiàn)這道題時，我們可以自頂而下，用遞歸進(jìn)行樹的遍歷求解,例

7、三 河流(IOI2005),一顆有N+1個結(jié)點的樹，樹中的每個結(jié)點可能會生產(chǎn)出一些產(chǎn)品。這些產(chǎn)品要么就地加工（要有加工廠才行），要么運送到它的父親結(jié)點那兒去?，F(xiàn)在在整棵樹的根結(jié)點處已經(jīng)有了一個產(chǎn)品加工廠，而且所有的產(chǎn)品最終必須在某個加工廠加工才行。由于運費昂貴，不可能將所有的產(chǎn)品都運送到根節(jié)點處加工?，F(xiàn)在決定在樹中的某些結(jié)點新增總共K個加工廠，現(xiàn)在要你選擇這K個加工廠的廠址。 假設(shè)結(jié)點i會生產(chǎn)出Wi噸產(chǎn)品，它的父結(jié)點是Pi。而它到它的父結(jié)點的路徑的長度是Ui。運費的計算是每運送1頓的貨物，每單位長度收取1的費用。根節(jié)點的編號為0。,例三 河流(IOI2005),例如右圖，0節(jié)點是根節(jié)點，如果要新增兩個工廠，最佳方案是建在2、3兩個節(jié)點上，這樣總的費用為： 1*1（1號）+1*3（4號）=4 由于題目中給出的樹是多叉樹，不便于進(jìn)行動態(tài)規(guī)劃。我們先利用兒子兄弟表示法，將多叉樹轉(zhuǎn)化為二叉樹。,進(jìn)行了相關(guān)的轉(zhuǎn)化之后，設(shè)f(i,j,k)表