1、樹狀動態(tài)規(guī)劃1DP在NOI中地位表中按照較優(yōu)算法標(biāo)準(zhǔn)分類的話，大致可分為五類，分別是數(shù)據(jù)結(jié)構(gòu)類：樹的遍歷，最短路徑，并查集，樹狀數(shù)組，哈希表，博弈樹；數(shù)學(xué)分析類：初等數(shù)論，解方程，邏輯推理，組合分析，線性代數(shù)；搜索類：寬度優(yōu)先搜索，回溯法；動態(tài)程序設(shè)計類；網(wǎng)絡(luò)流類 面臨的實際問題千奇百怪、數(shù)據(jù)模型千姿百態(tài)，求解方法千變?nèi)f化。要求選手“陣而后戰(zhàn)，兵法之常，運(yùn)用之妙，存乎一心”。 2知識點(diǎn)回顧是一個“多階段最優(yōu)化決策的過程”。即由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條最優(yōu)的活動路線 。動態(tài)規(guī)劃狀態(tài)（State）：表示事物的性質(zhì)

2、，是描述“動態(tài)規(guī)劃”中的“單元”的量。亦是每一階段求解過程的出發(fā)點(diǎn)。階段（Stage）：階段是一些性質(zhì)相近，可以同時處理的狀態(tài)集合，或者說，階段只是標(biāo)識那些處理方法相同、處理順序無關(guān)的狀態(tài)。3知識點(diǎn)回顧決策（Decision）：每個階段做出的某種選擇性的行動，是程序所需要完成的選擇。狀態(tài)轉(zhuǎn)移方程：是前一個階段的狀態(tài)轉(zhuǎn)移到后一個的狀態(tài)的演變規(guī)律，是關(guān)于兩個相鄰階段狀態(tài)變化的方程，是“動態(tài)規(guī)劃”的中心。設(shè)：fk(i)k階段狀態(tài)i的最優(yōu)權(quán)值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價： fk+1(i)=minxk(j)+u(i,j) DP應(yīng)該包含狀態(tài)、階段、決策、狀態(tài)轉(zhuǎn)移方程幾種基本關(guān)系與屬性。由于是按照階段的順

3、序，直接在子問題最優(yōu)解的基礎(chǔ)上計算的，“不做已經(jīng)做過的工作”，因此其效率比搜索法好得多。只要問題的計算過程呈階段性，且可找到狀態(tài)轉(zhuǎn)移方程，我們寧可摒棄傳統(tǒng)的搜索而采用動態(tài)程序設(shè)計方法。 4知識點(diǎn)回顧是指它要么是一棵空樹，要么它的左子樹的所有結(jié)點(diǎn)比根結(jié)點(diǎn)小，右子樹的所有結(jié)點(diǎn)比樹根結(jié)點(diǎn)大，它的左子樹和右子樹分別是一棵排序二叉樹。最大排序二叉樹是指在所有的排序二叉樹中節(jié)點(diǎn)最多的一棵樹。排序二叉樹二叉搜索樹二叉檢索樹二分檢索樹5知識點(diǎn)回顧根據(jù)關(guān)健碼值直接訪問。把關(guān)鍵碼映射到表中的一個位置來訪問記錄的過程。這個映射函數(shù)叫做哈希函數(shù)，在存放記錄的表叫做哈希表。也就是說，將所有元素存儲在一張表中，每一個元素

4、具有一個哈希函數(shù)，按照如下兩種方式給同一個哈希函數(shù)值的所有元素分配多個空間 哈希表（HashTable）6知識點(diǎn)回顧考慮哈希函數(shù)的因素有：計算哈希函數(shù)所需時間；關(guān)鍵字的長度；哈希表的大?。魂P(guān)鍵字的分布情況；記錄的查找頻率?？梢越?jīng)過較少的次數(shù)得到所查的元素，提高查詢的時間效率。 7知識點(diǎn)回顧四邊形不等式是Donald E. Knuth從最優(yōu)二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)中提出的。當(dāng)函數(shù)wi,j滿足：時，稱w滿足四邊形不等式。在動態(tài)規(guī)劃中被運(yùn)用于證明決策的單調(diào)性。四邊形不等式8知識點(diǎn)回顧二叉搜索樹可以實現(xiàn)任何一種基本的動態(tài)集合操作，但當(dāng)樹的高度時，這些操作性能可能變差，即不能保證在最壞的情況下動態(tài)集合操作的

5、時間為O(lg n)。這樣情況是因為二叉樹可能變得不平衡。用一組規(guī)則讓二叉樹平衡起來，例如，紅黑樹確保了沒有一條路徑會比任何其他路徑長到兩倍，因而基本上是平衡的。AVL樹應(yīng)用平衡化旋轉(zhuǎn)規(guī)則來完成指針結(jié)構(gòu)的修改。 平衡二叉樹9知識點(diǎn)回顧如果將初始狀態(tài)作為根結(jié)點(diǎn)，把從初始狀態(tài)的每一個可能棋步出發(fā)，進(jìn)行一輪游戲后得到的所有子狀態(tài)作為根結(jié)點(diǎn)的孩子結(jié)點(diǎn)；然后從這些新狀態(tài)出發(fā)進(jìn)行下一輪游戲，得到的又一批子狀態(tài)作為新狀態(tài)的孩子結(jié)點(diǎn)，依次類推，就可以根據(jù)游戲規(guī)則產(chǎn)生一棵包羅了各種可能狀態(tài)變化的樹，習(xí)慣上稱為博弈樹 博弈樹10知識點(diǎn)回顧奇數(shù)層的狀態(tài)由先行方進(jìn)行操作，偶數(shù)層的狀態(tài)由后行方進(jìn)行操作；從根結(jié)點(diǎn)到當(dāng)前狀

6、態(tài)的走步序列（路徑）表示了雙方依次輪流走過的棋步；葉子是游戲的終止?fàn)顟B(tài)（即狀態(tài)數(shù)為0或先前確定了取珠的洞口）。若葉子處在奇數(shù)層，后行方贏；若葉子處在偶數(shù)層，先行方贏；在對弈中，雙方都想贏，都會采取取勝的策略。 我們在博弈樹的每個結(jié)點(diǎn)上標(biāo)一個值F ，由這個值來確定操作方最佳的走法。不妨認(rèn)為，F(xiàn) 越大對先行方越有利，奇數(shù)層結(jié)點(diǎn)總是挑選使得值最大的方案走；而偶數(shù)層結(jié)點(diǎn)則恰好相反。由于子結(jié)點(diǎn)是由父結(jié)點(diǎn)推出來的，故父結(jié)點(diǎn)的值與其所有子結(jié)點(diǎn)的值有一定的關(guān)系。另一方面，游戲愈接近結(jié)束愈便于分析，也便于計算值。我們可從葉子結(jié)點(diǎn)出發(fā)，往上倒推每個結(jié)點(diǎn)的值，直至初始狀態(tài)的值為止。整棵博弈樹建立之后，便產(chǎn)生出取勝的

7、策略。博弈樹的特征構(gòu)造博弈樹的基本思想11樹狀動規(guī)某公司要舉辦一次晚會，但是為了使得晚會的氣氛更加活躍，每個參加晚會的人都不希望在晚會中見到他的上司，要不然他們會很掃興?，F(xiàn)在已知每個人的活躍指數(shù)和上司關(guān)系（當(dāng)然不可能存在環(huán)），求邀請哪些人來能使得晚會的總活躍指數(shù)最大。 back沒有上司的晚會12樹狀動規(guī)按照要求構(gòu)建一張關(guān)系圖，可見這是一棵樹。對于這類最值問題，向來是用動態(tài)規(guī)劃求解的。任何一個點(diǎn)的取舍可以看作一種決策，那么狀態(tài)就是在某個點(diǎn)取的時候或者不取的時候，以他為根的子樹能有的最大活躍總值。分別可以用fi,1和fi,0表示。back13樹狀動規(guī)當(dāng)這個點(diǎn)取的時候，他的所有兒子都不能取，所以fi

8、,1:=sum(fj,0,j為i的兒子)i的權(quán)值。不取的時候，他的所有兒子取不取無所謂，不過當(dāng)然應(yīng)該取價值最大的一種情況。所以fi,0:=sum(max(fj,1,fj,0),j為i的i兒子）。這就是樹狀動規(guī)的基本形態(tài)。back14樹狀動規(guī)大學(xué)里實行學(xué)分。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并考核通過就能獲得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門課的學(xué)分的總和。每個學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如，數(shù)據(jù)結(jié)構(gòu)必須在選修了高級語言程序設(shè)計之后才能選修。我們稱高級語言程序設(shè)計是數(shù)據(jù)結(jié)構(gòu)的先修課。

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

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

11、測，是不是可以以節(jié)點(diǎn)為階段，進(jìn)行動態(tài)規(guī)劃呢？我們用函數(shù)f(I,j)表示以第i個節(jié)點(diǎn)為父節(jié)點(diǎn)，取j個子節(jié)點(diǎn)的最佳代價，則：可是如此規(guī)劃，其效率與搜索毫無差別，雖然我們可以再次用動態(tài)規(guī)劃來使它的復(fù)雜度變?yōu)槠椒郊墸@得過于麻煩。分析19樹狀動規(guī)轉(zhuǎn)變?yōu)槎鏄?。如果兩?jié)點(diǎn)a,b同為兄弟，則將b設(shè)為a的右節(jié)點(diǎn)；如果節(jié)點(diǎn)b是節(jié)點(diǎn)a的兒子，則將節(jié)點(diǎn)b設(shè)為節(jié)點(diǎn)a的左節(jié)點(diǎn)。樹改造完成后如圖3。我們用函數(shù)f(I,j)表示以第i個節(jié)點(diǎn)為父節(jié)點(diǎn)，取j個子節(jié)點(diǎn)的最佳代價，這和前一個函數(shù)表示的意義是一致的，但方程有了很大的改變：023014765圖3改造樹20樹狀動規(guī)1=i=m,1=j=n,0=kj 這個方程的時間復(fù)雜度

12、最大為n3，十分優(yōu)秀了。在具體實現(xiàn)這道題時，我們可以自頂而下，用遞歸進(jìn)行樹的遍歷求解 轉(zhuǎn)移方程21問題研究例1、貨物儲運(yùn)問題back單調(diào)性的確定22在一個鐵路沿線順序存放著n堆裝滿貨物的集裝箱。貨物儲運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費(fèi)用與新的一堆中集裝箱數(shù)成正比。 給定各堆的集裝箱數(shù)，試制定一個運(yùn)輸方案，使總運(yùn)輸費(fèi)用最少。設(shè)合并ai:j，1ijn，所需的最少費(fèi)用為mi,j，則原問題的最優(yōu)值為m1，n。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，根據(jù)遞歸式，按通常方法可設(shè)計計算m(i,j)的O(n3)動態(tài)規(guī)劃算法貨物儲運(yùn)23貨物儲運(yùn)問題的動態(tài)規(guī)劃遞歸式是下面

13、更一般的遞歸計算式的特殊情形。對于 ,當(dāng)函數(shù)w(i,j)滿足時稱w滿足四邊形不等式。當(dāng)函數(shù)w(i,j)滿足 時稱W關(guān)于區(qū)間包含關(guān)系單調(diào) 對于滿足四邊形不等式的單調(diào)函數(shù)w，可推知由遞歸式定義的函數(shù)m(i,j)也滿足四邊形不等式，即四邊形不等式24四邊形不等式定義由函數(shù)m(i,j)的四邊形不等式性質(zhì)可推出函數(shù)s(i,j)的單調(diào)性，即根據(jù)前面的討論，當(dāng)w是滿足四邊形不等式的單調(diào)函數(shù)時，函數(shù)s(i,j)單調(diào)，從而 s(i,j) s(i,j+1) s(i+1,j+1)，i j改進(jìn)后算法所需的計算時間為 25問題研究例2LOSTCITY 用哈希表、檢索樹優(yōu)化DP26問題研究例3、排序二叉樹back狀態(tài)的存

14、儲27問題研究例4、取分（博弈樹與DP）博弈樹與DP28總結(jié)動態(tài)規(guī)劃有很多東西還需要我們更加努力地去探索和學(xué)習(xí).總體上說來,動態(tài)規(guī)劃是個既簡單又不簡單的算法,熟練地掌握了動態(tài)規(guī)劃,也就熟練地控制了比賽.back29練習(xí)題垃圾陷阱（USACO&TJU1087）卡門農(nóng)夫約翰極其珍視的一條Holsteins奶牛已經(jīng)落了到“垃圾井”中?！袄笔寝r(nóng)夫們?nèi)永牡胤剑纳疃葹镈 (2 = D = 100)英尺?？ㄩT想把垃圾堆起來，等到堆得與井同樣高時，她就能逃出井外了。另外，卡門可以通過吃一些垃圾來維持自己的生命。每個垃圾都可以用來吃或堆放，并且堆放垃圾不用花費(fèi)卡門的時間。假設(shè)卡門預(yù)先知道了每個垃圾

15、扔下的時間t(0 t = 1000)，以及每個垃圾堆放的高度h(1 = h = 25)和吃進(jìn)該垃圾能維持生命的時間f(1 = f = 30)，要求出卡門最早能逃出井外的時間，假設(shè)卡門當(dāng)前體內(nèi)有足夠持續(xù)10小時的能量，如果卡門10小時內(nèi)沒有進(jìn)食，卡門就將餓死。 30練習(xí)題字符串距離（TJU1086）設(shè)有字符串X，我們稱在X的頭尾及中間插入任意多個空格后構(gòu)成的新字符串為X的擴(kuò)展串，如字符串X為“abcbcd”，則字符串“abcbcd”，“abcbcd”和“abcbcd”都是X的擴(kuò)展串，這里“”代表空格字符。 如果A1是字符串A的擴(kuò)展串，B1是字符串B的擴(kuò)展串，A1與B1具有相同的長度，那么我們定義

16、字符串A1與B1的距離為相應(yīng)位置上的字符的距離總和，而兩個非空格字符的距離定義為它們的ASCII碼的差的絕對值，而空格字符與其它任意字符之間的距離為已知的定值K，空格字符與空格字符的距離為O。在字符串A、B的所有擴(kuò)展串中，必定存在兩個等長的擴(kuò)展串A1、B1，使得A1與B1之間的距離達(dá)到最小，我們將這一距離定義為字符串A、B的距離。 請你寫一個程序，求出字符串A、B的距離。 31練習(xí)題二叉蘋果樹（Ural1018）有一棵蘋果樹，如果樹枝有分叉，一定是分2叉（就是說沒有只有1個兒子的結(jié)點(diǎn)）這棵樹共有N個結(jié)點(diǎn)（葉子點(diǎn)或者樹枝分叉點(diǎn)），編號為1-N,樹根編號一定是1。我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號

17、來描述一根樹枝的位置。下面是一顆有4個樹枝的樹2 5 / 3 4 / 1現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。32練習(xí)題最長前綴 IOI96&USACO 1.4.3）在生物學(xué)中，一些生物的結(jié)構(gòu)是用包含其要素的大寫字母序列來表示的。生物學(xué)家對于把長的序列分解成較短的（稱之為元素的）序列很感興趣。如果一個集合 P 中的元素可以通過串聯(lián)組成一個序列 S ，那么我們認(rèn)為序列 S 可以分解為 P 中的元素。并不是所有的元素都必須出現(xiàn)。舉個例子，序列 ABABACABAAB 可以分解為下面集合中的元素： A, AB, BA, CA, BBC 序列 S 的前面 K 個字符稱作 S 中長度為 K 的前綴。設(shè)計一個程序，輸入一個元素集合以及一個大寫字母序列，計算這個序列最長的前綴的長度。 33練習(xí)題祝福（TJU1078）得知Atlantis即將沉沒的消息以后，King決定把他的人民送到安全的國外去。但是碼頭已經(jīng)廢棄很多很多年了。碼頭前有一個迷宮，國王的騎士只身闖入了這個迷宮 騎士在迷宮的出口遇到了不明生物的襲擊！騎士因為是單獨(dú)作戰(zhàn)，所以很快便招架不住了，他