動態(tài)規(guī)劃總結(jié)

1、-精品 word 文檔值得下載值得擁有 -動態(tài)規(guī)劃總結(jié)by Amber1. 按狀態(tài)類型分寫在前面：從狀態(tài)類型分， 并不表示一題只從屬于一類。 其實一類只是一種狀態(tài)的表示方法。 可以好幾種方法組合成一個狀態(tài)，來解決問題。1.1. 編號（長度）動態(tài)規(guī)劃共性總結(jié)本類的狀態(tài)是基礎(chǔ)的基礎(chǔ)，大部分的動態(tài)規(guī)劃都要用到它，成為一個維。一般來說，有兩種編號的狀態(tài)：狀態(tài) (i) 表示前 i 個元素決策組成的一個狀態(tài)。狀態(tài) (i) 表示用到了第 i 個元素，和其他在 1 到 i-1 間的元素，決策組成有的一個狀態(tài)。題庫a) 最長不下降子序列以一元組 (i) 作為狀態(tài)，表示第 i 個作為序列的最后一個點的時候的最長序

2、列。于是很容易想到 O(n2) 得算法。但本題可 合理組織狀態(tài) ，引入一個單調(diào)的輔助數(shù)組，利用單調(diào)性二分查找，優(yōu)化到 O(nlogn) 。關(guān)于優(yōu)化詳見優(yōu)化章。一些問題可將數(shù)據(jù)有序化 ，轉(zhuǎn)化成本題。應(yīng)用：攔截導(dǎo)彈 (NOIP99 Advance 1)就是原題。Beautiful People (sgu199) ，要將數(shù)據(jù)有序化：其中一個權(quán)作為第一關(guān)鍵字不下降排列，另一個權(quán)作為第二關(guān)鍵字不上升。Segment(ural 1078)，將線段的左端點有序化就可以了。b) LCS狀態(tài) (i,j) ，表示第 1 個字符串的第 i 位，與第 2 個字符串的第 j 位匹配，得到的最長的串。若有多個串要 LCS

3、，則加維，即幾個串就幾個維。我也將此題歸入路徑問題。c) 花店櫥窗布置 (IOI99)見路徑問題。1.2. 區(qū)間動態(tài)規(guī)劃共性總結(jié)本類問題與下一章的 劃分問題 的決策的分割點無序 交集比較大（占本類問題的 30%）。-精品 word 文檔值得下載值得擁有 -精品 word 文檔值得下載值得擁有 -題庫a) 石子合并見劃分問題b) 模版匹配 (CEOI01,Patten)這題特殊的地方是狀態(tài)的值是一個集合而不是一個數(shù)。c) 不可分解的編碼 (ACM World Final 2002)d)Electric Path(ural1143)e) 郵局 (IOI2000 Day2 1)若狀態(tài)表示的思路從第

4、i 個村莊可以從屬于哪個郵局，無最優(yōu)子結(jié)構(gòu)。轉(zhuǎn)變一個方向：第 k 個郵局可以“控制”一個區(qū)間的村莊 i,j 。于是方程就顯然了 :f(k,i,j)=minf(k-1,p,i-1)+w(i,j)(k-1<=p<=i-1)S(i) 為村莊 i到原點的距離。w(i,j)=mink|Sum|S(k)-S(p)|(i<=p<=j)(i<=k<=j)找到 i,j間最好的一個郵局點。不過可以發(fā)現(xiàn)Sum|S(k)-S(p)|是單調(diào)的，所以取中位數(shù)就可以了。即上式中 k 的取值范圍只有 floor(i+j)/2), ceil(i+j)/2)兩個。Floor 是下取整。 Cei

5、l是上取整。這樣每次轉(zhuǎn)移時間降到O(1) 。注意到是區(qū)間連續(xù)的，即(p,i-1)和 (i, j)中的 i-1, i是連續(xù)的，所以空間可以降維： f(i,j)表示放前 i 個郵局到前 j 個村莊的最優(yōu)值。f(i,j)=minf(i-1,p-1)+w(p,j)(i-1<=p<=j-1e(i,j) 為當(dāng) f(i,j)到達最優(yōu)值時的p.通過證明四邊形不等式，得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)決策數(shù)量又少了一個數(shù)量級。1.3. 坐標(biāo)動態(tài)規(guī)劃共性總結(jié)之后的一些問題，狀態(tài)是由坐標(biāo)維與其他的維組成。本類與 劃分問題 ( 是 2 維或多維的坐標(biāo)系的劃分 ) 與路

6、徑問題 的交集占本類問題中大多數(shù)。題庫a) 棋盤分割 (NOI99 4)主要是將公式變形，變形后的公式很容易看出方程。狀態(tài)是由 2 個坐標(biāo)組成的4 元組 (x1,y1)(x2,y2)，表示一個子棋盤。這有點像之前的區(qū)間動態(tài)規(guī)劃，只不過是將1維轉(zhuǎn) 2維。后見路徑問題。1.4. 數(shù)軸動態(tài)規(guī)劃共性總結(jié)題庫a) 01 背包-精品 word 文檔值得下載值得擁有 -精品 word 文檔值得下載值得擁有 -應(yīng)用：裝箱問題 （NOIP01 Trade 4 ）就是原題。值幣分割可利用方程的性質(zhì)，空間降1 維。幣值可重復(fù)的值幣分割(pku1742, Problem F LouTianChengs Contest

7、 in POJ)使用左右法在定位上加速。另給狀態(tài)加一個屬性 last, 記錄上一次剩下的可用的同幣值硬幣數(shù)（利用了當(dāng)前轉(zhuǎn)移是唯一前驅(qū)的特點）。b) 取火柴問題 (sgu153 Playing with matches)c) Stone Pile (ural1005 Stone Pile)d) 公路巡邏 (CTSC2000)1.5. 5.樹型動態(tài)規(guī)劃共性總結(jié)1） 動態(tài)規(guī)劃的順序一般按照后序遍歷的順序，即處理完兒子再處理當(dāng)前節(jié)點，才符合樹的子結(jié)構(gòu)的性質(zhì)。2） 多叉樹轉(zhuǎn)換為二叉樹由于要分配附加維到各個節(jié)點， 而分配附加維是個劃分問題， 若還是按當(dāng)前節(jié)點到各個兒子節(jié)點分配，則成了一個 整數(shù)劃分 問題

8、,O(n 2) 。所以要把多叉樹轉(zhuǎn)換為二叉樹，這樣才能按動態(tài)規(guī)劃的方式只決策當(dāng)前點的分配問題, O(n) 。3） 加當(dāng)前點的選或不選的常數(shù)維加此維解決的是后效性問題。,4） 在將邊信息轉(zhuǎn)成樹時的技巧將讀入的邊分裂成 2 條邊，將這 2 條邊關(guān)聯(lián)起來（就是找到一條邊，另一條邊的編號就知道）。用 前向星表示法 表示邊（按起點有序），以后用邊的時候，用了一條邊打不可用標(biāo)志，也將關(guān)聯(lián)邊打不可用標(biāo)志。這樣可以保證 O(n) 的時間完成信息處理，而且在父節(jié)點找兒子的過程中帶來很大的方便。5） 復(fù)雜度樹型動態(tài)規(guī)劃復(fù)雜度基本上是O(n) ；若有附加維 m，則是 O(nm)。題庫a) 選課 (CTSC97-3)

9、由于要分配課程數(shù)，所以要多叉樹轉(zhuǎn)換為二叉樹。b) 貪吃的九頭龍 (NOI02-3)若小頭數(shù)大于 1 的話，則讓不同的小頭吃一段樹枝的 2 個端點。這樣就把問題轉(zhuǎn)化成：附加維是大頭吃的個數(shù)，當(dāng)前點由不由大頭吃的常數(shù)維的動態(tài)規(guī)劃。由于涉及劃分問題，所以要多叉樹轉(zhuǎn)換為二叉樹。c) 求樹的質(zhì)心 (sgu134 Centroid)-精品 word 文檔值得下載值得擁有 -精品 word 文檔值得下載值得擁有 -給出一棵邊不帶權(quán)的樹， 求點 , 使得去掉此點后 , 剩下的最大的連通子圖的頂點數(shù)最小 .d) 求樹中的點最遠距離最近。給出一棵邊帶權(quán)的樹，求樹中的點，使得此點到樹中的其他結(jié)點的最遠距離最近。Co

10、mputer Network (sgu149)Computer Net (ural1056)1.6. 集合動態(tài)規(guī)劃（狀態(tài)壓縮）共性總結(jié)1) 數(shù)據(jù)特殊性給出的數(shù)據(jù)在某一個或幾個維度上一般具有比較小的范圍（可以枚舉一類的狀態(tài)）。一個枚舉的狀態(tài)是一個集合。2) 編碼由于集合中元素個數(shù)的不定性或范圍大， 直接開數(shù)組存， 不好索引數(shù)組 （編程復(fù)雜度太高），所以要將集合編碼。利用數(shù)據(jù)的可枚舉性， 將枚舉的狀態(tài) ( 集合 ) 編碼。一般來說碼值的范圍要很小 （盡量排除無用的碼值，如炮兵：當(dāng)前格和上格存在炮兵的情況是非法的， 可以排除）。規(guī)定編碼的碼值代表的意思，要盡量規(guī)定好維護的碼值。（如炮兵： 當(dāng)前格存在

11、炮兵的用 2，上格存在炮兵用 1。這樣下一層的規(guī)劃時，只要碼值 -1 即可）。有時候可以直接利用編碼的順序動態(tài)規(guī)劃，因為這時編碼已經(jīng)是拓補有序 。如 TSP問題當(dāng)前已選點集合的狀態(tài)的前驅(qū)的編碼的值一定比當(dāng)前的編碼的值小。3) 狀態(tài)壓縮對有限階段的放置情況，行走情況編碼（其實質(zhì)也是放置的集合或行走路線的集合），這樣的編碼，也有人謂之：“狀態(tài)壓縮”。此類題以“炮兵陣地”為典型，進行擴展。題庫a) 購物（ IOI95-2 ）可將每種物品按 5 進制編碼。（ 5 為每種物品數(shù)的上限）由于物品數(shù)的上限為5，比較小，也可直接開數(shù)組存。b) Roger 游戲任務(wù)一 （CTSC98 Day2 4）一個正方體在

12、一個方格內(nèi)的狀態(tài)只有 24 種，而且可以通過頂面和前面來表示，這樣用 3 維的狀態(tài) (x,y,p) 就可以解決， p 為 1 到 24 種狀態(tài)中的一種。c)TSP問題觀察一下 TSP的搜索過程： for (x in未選點 ) TSP(x)即當(dāng)前路的最后一個節(jié)點為x, 現(xiàn)在要選擇下一個節(jié)點y, 而 y 要在未選點的集合中。若未選點或已選點的集合已確定，則后效性消除?？梢訢P。狀態(tài)為令X 為當(dāng)前路的已選點的集合 ( 含 i) ，當(dāng)前路的最后一個節(jié)點為i 。2 元組 (X,i)為經(jīng)過已選點的集合 X 到節(jié)點 i 的最短長度。將 X 編碼即可。注意：并沒有因為動態(tài)規(guī)劃將問題從NP類帶到 P 類。應(yīng)用

13、:DNA Laboratory (Problem B,TU-Darmstadt Programming Contest 2004)-精品 word 文檔值得下載值得擁有 -精品 word 文檔值得下載值得擁有 -將每個串的交迭部分求出，就可以將問題專成TSP但要輸出字典序最小的，則需要注意DP順序。有具體的報告。d) 炮兵陣地十分經(jīng)典，詳見報告 。應(yīng)用 :AnotherChocolate Maniac (sgu132)類似炮兵的做法的最值，只不過是求最小值，麻煩點。Hardwoodfloor (sgu131)類似炮兵的做法的統(tǒng)計LittleKnights (sgu225)類似炮兵的做法的統(tǒng)計

14、, 數(shù)據(jù)量太大要 constLittleKings (sgu223)類似炮兵的做法的統(tǒng)計Bugs 公司 (CEOI 2002)類似炮兵的做法的最值1.7. 利用動態(tài)規(guī)劃思想求最值，編號（循環(huán)變量）的迭代共性總結(jié)要利用上次的一些運算“剩下”的循環(huán)變量作當(dāng)前循環(huán)的邊界，主要在于找出一種決策順序，使之成立。題庫a) 奶牛浴場b) Communication System將數(shù)據(jù)有序化 , 從大到小枚舉帶寬 , 每次可利用上次處理的結(jié)果 Min, 來決策當(dāng)前狀態(tài)。稱作迭代 , 或就是一種動態(tài)規(guī)劃。(zju1409, Problem C Tehran 2002 Iran NationwideInterne

15、t Programming Contest)1.8. 記憶化搜索題庫a)Magic Trick(Problem G, TU-Darmstadt Programming Contest 2004)2. 按轉(zhuǎn)移方式分2.1. 存在性遞推1)01 統(tǒng)計 (CTSC99 1)2)卡特蘭數(shù)-精品 word 文檔值得下載值得擁有 -精品 word 文檔值得下載值得擁有 -circle(sgu130)3)鷹蛋2.2. 求一系列的分割（合并）點（劃分問題）2. 2.1. 決策的分割點有序共性總結(jié)a) 有序性每次決策的點的編號是有序的，即要按決策的順序輸出分割點的編號的話，編號是有序的，滿足分割點的編號按升序排

16、列。b) 方程一般形式f(n,m)=optimizef(k,m-1)+w(k+1,n)(n,m)表示從 1 到 n 個點中劃分為 m個部分的最優(yōu)值； k 為決策的分割點，即第 m個部分為 k+1 到 n；這里 optimize 可以為 max,min。題庫a) 整數(shù)劃分常應(yīng)用在將一個權(quán)分配給一定的小分割塊， 如：將大堆的石子分成一定的小堆， 小堆可為空，大堆要分完。有時應(yīng)用在樹型動態(tài)規(guī)劃（二叉轉(zhuǎn)多叉）中。b) 乘積最大 (NOIP00 Advance 2)就是按上面的一般式的方程做。決策的分割點無序共性總結(jié)a) 無序性每次決策的點的編號是無序的， 即要按決策的遞歸順序輸出分割點的編號的話，編號

17、是無序的。b) 方程一般形式f(i,j)=optimizef(i,k-1)+f(k+1,j)+w(i,j)(i,j) 表示從 i 到 j 的范圍內(nèi)選取一個分割點 k 的最優(yōu)值，子問題是分割點左邊 (i,k-1) 和右邊 (k+1,j) 的點的范圍的最優(yōu)值； 這里 optimize 可以為 max,min。方程很類似 2 叉樹的性質(zhì)。c) 四邊形不等式此類的問題，有些可用四邊形不等式優(yōu)化。見優(yōu)化章。題庫a) 石子合并 (NOI95 2)經(jīng)典，詳見報告。2可用四邊形不等式優(yōu)化成O(n )其實還可以用類似堆的數(shù)據(jù)結(jié)構(gòu)在O(nlogn) 的時間內(nèi)完成， 但這就不是動態(tài)規(guī)劃了。-精品 word 文檔值得

18、下載值得擁有 -精品 word 文檔值得下載值得擁有 -應(yīng)用：構(gòu)造最優(yōu)二叉排序樹(CTSC96 2)b) 多邊形 (IOI98)這題值的正負號處理要注意，乘法運算， 由于符號的加入，使原本的正的最優(yōu)解， 一下變成負的。c) 加分二叉樹 (NOIP03 Advance 3)方程就是一般式， 轉(zhuǎn)移的函數(shù)： w(i,j)=sum(i,k-1)*sum(k+1,j)+d(k)。由于 w(i,j)不滿足凸單調(diào)性，所以不能用四邊形不等式優(yōu)化。d) 括號序列 (Problem B, NEERC 2001)這題的分割點不是一個元素，而是元素間的一條線。主要的思維方式是從遞歸定義。2.3. 路徑問題共性總結(jié)a) 行走方向決定階段性有規(guī)定源點與終點。 每次行走方向都有一定的規(guī)定， 使原點到終點的所有路徑形成無環(huán)有向圖。b) 多源或多匯