1、淺析NOIP范圍內的DP算法2009-08-12 10:03一、NOIP中，DP的出題方向近年來，DP已成為NOIP中的“必考”項目，在06年的提高組題目中，甚至出現了兩題DP（且該年分數線約為130分），DP的重要性可見一斑。由于NOIP的難度所限，所出的DP基本上都是一些典型的模型加以稍許改編。如下：2003：加分二叉樹：樹型動態規劃（區間類）。2004：合唱隊形：雙向最長不降（升）序列。2005：過河：需壓縮空間的線性動態規劃。2006：能量項鏈：環狀的合并類；金明的預算：需分類以取消后效性的01背包問題。2007：矩陣取數：需高精度的區間類動態規劃。由此可見，NOIP在DP一塊上的出題

2、思路基本上是：不出刁鉆的，罕見的動態規劃類型，模式通常較易識別，但添加了部分新難點，以增加題目的區分度。這也就要求我們在復習DP算法時，集中注意力在一些典型的模型，以及了解其本質，才能拿下稍作變形的真題。二、一些經典的DP模型一道DP往往可以通過多種方式去做，所以以下分類并不完全準確，是相對而言的。大家不要死記某種類型，而應把握該類題型的本質和共性。1）不降（升）序列類&線性類不降序列問題相信大家都做過。它的特點是線性遞推，通常以某一結點為狀態，轉移是由前往后線性遍歷。典型題目有導彈攔截和過河。由于大家都很熟悉了，加上今年來NOIP出了好幾回，這里不做多說。特別留意：1. 不降（升）序

3、列的O(nlogn)算法。（）2. 不降（升）序列中的方案個數。（)3. 對于大數據可能需根據實際進行壓縮，主要通過轉移方程決定。（*可能用到“維護”思想，）4. 線性類題目可以隱藏得很深，構建模型時需多加留意能否用線性DP做。（）2）背包類背包類問題也是大家常見的類型。它的特點是以前幾樣物品組成的集合為狀態，決策也很明顯“取”與“不取”。背包類問題的變形十分多，這里強烈建議大家抽時間去看著名的背包九講，里面寫得相當詳盡，掌握里面的內容后，背包類基本上不用擔憂了。（）特別留意：1.要保證無后效性，遇到設置后效性的題目可以分類處理（如金明的預算）。2.如有多維，且維數太多，則考慮降低每次循環的次

4、數或考慮其他思路。3.在實現算法時，如果狀態轉移只在相鄰兩三個階段間發生，則可用動態數組，可以減少空間需要。4.背包類題目也可以出得很隱蔽，比如多米諾骨牌問題，重要的是抽取模型。（見）5.需特別注意解數組的初始值設定，弄清楚解為0與無解的區別，常把初始值設為無窮小，也可都設為0，再在引用時判斷是否是無解。3） 路徑類路徑類的典型例題有三角取數和花店櫥窗布置。其特點是決策是“左走”，“右走”或“直走”。這類題目是十分典型的DP模型，但已有幾年沒出了，需留意。特別留意：1.注意邊界的設置。2.實現算法時可用動態數組，減少空間。3.若題目設置“時間”概念，可能需要加維。4）區間&合并類區間類

5、問題可以看做一個連續的大區間被分割成若干個有重疊的小區間，再從中選擇最優解，而選擇的依據就是轉移方程。由于這種題長度為L的區間需要引用到長度不足L的區間的結果，所以常以長度作為階段，起始位置為狀態。合并類是在區間類基礎上，以最佳合并為選擇依據的一類題目。這類題目分別出在了06年和07年考題上能量項鏈和矩陣取數，今年再出的可能性相對不大，但也不可輕視。特別留意：1.如遇環狀模型，可從任意一結點斷開，在后方補足，使之成為線性。（）2.轉移方程中，可能有需要預處理的內容，或用貪心算法。    （）5） 樹型樹型動態規劃，就是指建立在樹這個數據結構上的動態規劃。它的特點是

6、以單個結點為狀態，轉移方程有該結點的孩子參與，計算過程自下往上進行。上一次出此類題目是5年前，說不準今年就會出。它的典型例題有選課和戰略游戲。（）特別留意：1.掌握好樹的讀入方式，以及多叉樹變二叉樹的方式。2.因為樹的特殊結構，經常要分類討論一個結點在做決策時的各種可能性，需要小心處理，考慮周全。（）6）布爾型這是一種相對少見的類型，其實還是屬于背包類或線性類，只是它的最優值數組是布爾類型，所以我將其獨立為一類。它的特點是最優解數組的類型為布爾類型，轉移方程為邏輯運算，實際的問題最優解藏在狀態之中。典型的題有砝碼問題和取余問題（）特別留意：1.使用前，要論證可以使用此類DP。2.取余類問題中，

7、狀態設置應為-(m-1).(m-1)或0.(m-1)。7） 坐標類這種類型也很少見，而且難度通常較大，不必過于關注。其特點是：在平面或立體內，以點坐標或相應矩形為狀態。典型問題有棋盤分割和奶牛浴場。特別留意：1.此類題目往往根據幾何關系或數學知識推斷出轉移方程。8） 集合狀態類這種類型也不多見，但特點很突出。它往往具有多個狀態維數，有時多達5，6個，而且決策與若干個狀態組成一個整體，修改最值時一同更新。典型例題有購物和快餐問題。特別留意：1.確定使用此類DP后，大膽增設狀態維數。2.要找出切實可行的轉移方程和算法實現方式。9）字符串類字符串類問題也不是一個專門的DP類型，這里專指一些利用到字符

8、串特點的DP問題，如最長公共子序列和調整隊形。它往往是兩個字符串按一定的規則匹配，從而得到一系列最優解。常用的方法是以一個字符串中的一個字符去匹配另一個字符串的前面若干個字符構成的子串。（）特別留意：1.要確定最優解的狀態的所有可能性。2.多數時候此類問題還是屬于線性類問題，需要結合線性類的特點設計算法。3.可留意一下KMP算法。4.可留意一下回文字一類題目。三、NOIP可能會給模型增加的難度1）非線性數據類型在數據類型方面，NOIP最可能增添的難度是出環狀和樹狀。1. 樹狀對于樹狀，我們通常可以用樹型DP解決。需留意的是，有些看似樹型DP的題，其實可能是區間類DP，如03年的加分二叉樹。另外

9、，樹的輸入方式有很多種，我們必須熟悉如何恰當保存樹的數據，否則即便會做DP也拿不了分。2. 環狀對于環狀，我們有兩種處理方法將其破壞成鏈：    (1) 確定某結點為起點，枚舉該結點狀態，每次枚舉后DP求解，記錄起點為該狀態下得到的最優解。最后將各種可能的最優解篩選出問題的最優解。此類方法適用于線性DP和路徑型DP。(2) 對于長度為n的環，任意選取一點為起點，由起點開始得到一條長度為n的鏈，將前面n-1長度的鏈復制并轉移到鏈的末端，相當于將兩條同樣的鏈首尾相接。由此，環的任意一種單向遍歷方式都可以在這個長度為2n-1的鏈中實現。此類方法適用于區間類DP。

10、0;   從本質上講，這兩種處理方式是完全一樣的，既枚舉起點的位置或狀態，利用DP求解。需要留意的是，這種條件下的最優值的位置往往要特別考慮的。2）結合其他算法1. 貪心DP和貪心結合的例子很常見,有以下兩種:（1）通過貪心確定轉移方程，也可以作為預處理部分。例題為郵局。      （）（2）通過貪心確定最優解的上限或下限，從而減少循環量，在大規模數據時很有效。例題為快餐問題。2. 搜索搜索和DP的結合，可以體現在兩方面：（1） 記憶化搜索所謂“記憶化搜索”就是在傳統的搜索過程中，加入DP的“保留子問題最優解”思想，提高時間

11、效率。從框架上講，還是搜索算法，這里不作討論。（2） 搜索中的局部進行DP求解在搜索過程中，某個局部可能用到DP進行求解。例題為郵票面值設計。（）3. 字符串處理、高精度、排序、求質數等這幾樣都是基礎算法，可作為DP的預處理，這里不多做敘述。3）提出其他任務1. 輸出最優方案這是很常見的一種題目要求，它不僅要求我們求出最優值的大小，還要確定與之對應的每個決策。通常有兩個方法解決： 增添記錄每次決策的數組M。在每次做決策時，M中對應的狀態也保留一個代表該決策的值。如01背包中，某個背包取或不取，M中對應的值為1或0。在得出最優解后，正向遍歷M（構建隊列）或逆向遍歷M（構建棧），從而輸出最優方案。

12、 一些題目的性質決定，在得出最優解后，可以通過貪心輸出最優方案。如書的復制     （)前一種方法具有普遍性，在時空允許下絕大部分DP題目適用。后一種題目在小范圍內適用，但其編程復雜度和時空復雜度都相當理想。2. 求前k優解（方案）或第k優解（方案）此問題可通過增設狀態維數解決。在最優解數組中增加一維p表示同樣狀態下的第p優解，顯然在DP過程中，只需保留每個狀態的前k優解就足夠。在狀態轉移時，算出新狀態的前k個最優解，依次保存。需要注意的是，每一種可以得出新狀態的前k個最優解的情況都要考慮到。另外，題目可能問前k個最優解（數字一樣時當一種解，中間的策略不

13、用考慮），也可能問前k個最優方案（不僅數字一樣，而且策略也一樣），做題時要加以區分。3. 求最優方案的個數這個問題可以用1）和2）中的思想共同解決。增設數組C，表示一定狀態下的最優方案的個數，在狀態轉移時，小心疊加即可。4. 同時問兩類最優值有時題目會要求兩類最優值A和B。遇到這樣的問題，要分清楚其依賴關系，比如題目實際要求輸出A的最優解，以及在A最優的情況，B的最優解。如此一來我們依然以B為狀態，A為實際的最優解進行DP求解。同時我們增設一個數組Q，在計算A的過程中，在保證A最優的情況下，保存最優的B；遇到更優的A時，也更新B的最優解。例題為找GF。（）4） 增設小范圍的后效性如果你看到一道很熟悉的DP題，但又發現它在小范圍內有后效性，那么也許在進行簡單處理后，這題依然可以用DP求解。這類題目類型有二：1. 具后效性的狀態與它控制的狀態成主次關系典型的例子為金明的預算方案，若干狀態被一個狀態控制，那么可以把這幾個狀態連同控制它的狀態作為一個類，將題目的所有狀態分成若干個類進行處理。每個類中，如果要選擇當中的次級狀態，必須先選中它所依賴的狀態。也可以理解成將題目各狀態轉化為樹的形式進行DP，若要選擇一個結點，必先選擇它的父母，而兄弟間是沒聯系的。 2. 具后效性的狀態與它控制的狀態成并列關系5) 多進程問題