淺析NOIp范圍內(nèi)的DP算法

1、淺析NOIP范圍內(nèi)的DP算法深圳市龍城高級中學劉偉潛1.NOIP中,DP的出題方向近年來,DP已成為NOIP中的“必考”項目,在06年的提高組題目中,甚至出現(xiàn)了兩題DP(且該年分數(shù)線約為130分,DP的重要性可見一斑。由于NOIP的難度所限,所出的DP基本上都是一些典型的模型加以稍許改編。如下:2003:加分二叉樹:樹型動態(tài)規(guī)劃(區(qū)間類。2004:合唱隊形:雙向最長不降(升序列。2005:過河:需壓縮空間的線性動態(tài)規(guī)劃。2006:能量項鏈:環(huán)狀的合并類;金明的預算:需分類以取消后效性的01背包問題。2007:矩陣取數(shù):需高精度的區(qū)間類動態(tài)規(guī)劃。由此可見,NOIP在DP一塊上的出題思路基本上是:

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

3、性,遇到設置后效性的題目可以分類處理(如金明的預算。2.如有多維,且維數(shù)太多,則考慮降低每次循環(huán)的次數(shù)或考慮其他思路。3.在實現(xiàn)算法時,如果狀態(tài)轉(zhuǎn)移只在相鄰兩三個階段間發(fā)生,則可用動態(tài)數(shù)組,可以減少空間需要。4.背包類題目也可以出得很隱蔽,比如多米諾骨牌問題,重要的是抽取模型。5.需特別注意解數(shù)組的初始值設定,弄清楚解為0與無解的區(qū)別,常把初始值設為無窮小,也可都設為0,再在引用時判斷是否是無解。3路徑類路徑類的典型例題有三角取數(shù)和花店櫥窗布置。其特點是決策是“左走”,“右走”或“直走”。這類題目是十分典型的DP模型,但已有幾年沒出了,需留意。特別留意:1.注意邊界的設置。2.實現(xiàn)算法時可用動

4、態(tài)數(shù)組,減少空間。3.若題目設置“時間”概念,可能需要加維。4區(qū)間&合并類區(qū)間類問題可以看做一個連續(xù)的大區(qū)間被分割成若干個有重疊的小區(qū)間,再從中選擇最優(yōu)解,而選擇的依據(jù)就是轉(zhuǎn)移方程。由于這種題長度為L的區(qū)間需要引用到長度不足L的區(qū)間的結果,所以常以長度作為階段,起始位置為狀態(tài)。合并類是在區(qū)間類基礎上,以最佳合并為選擇依據(jù)的一類題目。這類題目分別出在了06年和07年考題上能量項鏈和矩陣取數(shù),今年再出的可能性相對不大,但也不可輕視。特別留意:1.如遇環(huán)狀模型,可從任意一結點斷開,在后方補足,使之成為線性。2.轉(zhuǎn)移方程中,可能有需要預處理的內(nèi)容,或用貪心算法。5樹型樹型動態(tài)規(guī)劃,就是指建立在

5、樹這個數(shù)據(jù)結構上的動態(tài)規(guī)劃。它的特點是以單個結點為狀態(tài),轉(zhuǎn)移方程有該結點的孩子參與,計算過程自下往上進行。上一次出此類題目是5年前,說不準今年就會出。它的典型例題有選課和戰(zhàn)略游戲。特別留意:1.掌握好樹的讀入方式,以及多叉樹變二叉樹的方式。6布爾型這是一種相對少見的類型,其實還是屬于背包類或線性類,只是它的最優(yōu)值數(shù)組是布爾類型,所以我將其獨立為一類。它的特點是最優(yōu)解數(shù)組的類型為布爾類型,轉(zhuǎn)移方程為邏輯運算,實際的問題最優(yōu)解藏在狀態(tài)之中。典型的題有砝碼問題和取余問題特別留意:1.使用前,要論證可以使用此類DP。2.取余類問題中,狀態(tài)設置應為-(m-1.(m-1或0.(m-1。7坐標類這種類型也很

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

7、還是屬于線性類問題,需要結合線性類的特點設計算法。3.可留意一下KMP算法。4.可留意一下回文字一類題目。3.NOIP可能會給模型增加的難度1非線性數(shù)據(jù)類型在數(shù)據(jù)類型方面,NOIP最可能增添的難度是出環(huán)狀和樹狀。1樹狀對于樹狀,我們通?？梢杂脴湫虳P解決。需留意的是,有些看似樹型DP的題,其實可能是區(qū)間類DP,如03年的加分二叉樹。另外,樹的輸入方式有很多種,我們必須熟悉如何恰當保存樹的數(shù)據(jù),否則即便會做DP也拿不了分。2環(huán)狀對于環(huán)狀,我們有兩種處理方法將其破壞成鏈:1.確定某結點為起點,枚舉該結點狀態(tài),每次枚舉后DP求解,記錄起點為該狀態(tài)下得到的最優(yōu)解。最后將各種可能的最優(yōu)解篩選出問題的最優(yōu)

8、解。此類方法適用于線性DP和路徑型DP。2.對于長度為n的環(huán),任意選取一點為起點,由起點開始得到一條長度為n的鏈,將前面n-1長度的鏈復制并轉(zhuǎn)移到鏈的末端,相當于將兩條同樣的鏈首尾相接。由此,環(huán)的任意一種單向遍歷方式都可以在這個長度為2n-1的鏈中實現(xiàn)。此類方法適用于區(qū)間類DP。從本質(zhì)上講,這兩種處理方式是完全一樣的,既枚舉起點的位置或狀態(tài),利用DP求解。需要留意的是,這種條件下的最優(yōu)值的位置往往要特別考慮的。2結合其他算法1貪心DP和貪心結合的例子很常見,有以下兩種:1.通過貪心確定轉(zhuǎn)移方程,也可以作為預處理部分。例題為郵局。2.通過貪心確定最優(yōu)解的上限或下限,從而減少循環(huán)量,在大規(guī)模數(shù)據(jù)時

9、很有效。例題為快餐問題。2搜索搜索和DP的結合,可以體現(xiàn)在兩方面:1.記憶化搜索所謂“記憶化搜索”就是在傳統(tǒng)的搜索過程中,加入DP的“保留子問題最優(yōu)解”思想,提高時間效率。從框架上講,還是搜索算法,這里不作討論。2.搜索中的局部進行DP求解在搜索過程中,某個局部可能用到DP進行求解。例題為郵票面值設計。3字符串處理、高精度、排序、求質(zhì)數(shù)等這幾樣都是基礎算法,可作為DP的預處理,這里不多做敘述。3提出其他任務1輸出最優(yōu)方案這是很常見的一種題目要求,它不僅要求我們求出最優(yōu)值的大小,還要確定與之對應的每個決策。通常有兩個方法解決:1.增添記錄每次決策的數(shù)組M。在每次做決策時,M中對應的狀態(tài)也保留一個

10、代表該決策的值。如01背包中,某個背包取或不取,M中對應的值為1或0。在得出最優(yōu)解后,正向遍歷M(構建隊列或逆向遍歷M(構建棧,從而輸出最優(yōu)方案。2.一些題目的性質(zhì)決定,在得出最優(yōu)解后,可以通過貪心輸出最優(yōu)方案。如書的復制前一種方法具有普遍性,在時空允許下絕大部分DP題目適用。后一種題目在小范圍內(nèi)適用,但其編程復雜度和時空復雜度都相當理想。2求前k優(yōu)解(方案或第k優(yōu)解(方案此問題可通過增設狀態(tài)維數(shù)解決。在最優(yōu)解數(shù)組中增加一維p表示同樣狀態(tài)下的第p 優(yōu)解,顯然在DP過程中,只需保留每個狀態(tài)的前k優(yōu)解就足夠。在狀態(tài)轉(zhuǎn)移時,算出新狀態(tài)的前k個最優(yōu)解,依次保存。需要注意的是,每一種可以得出新狀態(tài)的前k

11、個最優(yōu)解的情況都要考慮到。另外,題目可能問前k個最優(yōu)解(數(shù)字一樣時當一種解,中間的策略不用考慮,也可能問前k個最優(yōu)方案(不僅數(shù)字一樣,而且策略也一樣,做題時要加以區(qū)分。3求最優(yōu)方案的個數(shù)這個問題可以用1和2中的思想共同解決。增設數(shù)組C,表示一定狀態(tài)下的最優(yōu)方案的個數(shù),在狀態(tài)轉(zhuǎn)移時,小心疊加即可。4同時問兩類最優(yōu)值4增設小范圍的后效性如果你看到一道很熟悉的DP題,但又發(fā)現(xiàn)它在小范圍內(nèi)有后效性,那么也許在進行簡單處理后，這題依然可以用 DP 求解。 這類題目類型有 2： 1）具后效性的狀態(tài)與它控制的狀態(tài)成主次關系 具后效性的狀態(tài)與它控制的狀態(tài)成主次關系 典型的例子為金明的預算方案 若干狀態(tài)被一個狀態(tài)控制， 金明的預算方案， 那么可以把這幾個狀態(tài)連同 金明的預算方案 控制它的狀態(tài)作為一個類，將題目的所有狀態(tài)分成若干個類進行處理。每個類中，如果要選 擇當中的次級狀態(tài)， 必須先選中它所依賴的狀態(tài)。 也可以理解成將題目各狀態(tài)轉(zhuǎn)化為樹的形 式進行 DP，若要選擇一個結點，必先選擇它的父母，而兄弟間是沒聯(lián)系的。 2）具后效性的狀態(tài)與它控制的狀態(tài)成并列關系 具后效性的狀態(tài)與它控制的狀態(tài)成并列關系 5）多進程問題 多進程問題 不能多次 DP，必須增設狀態(tài)維數(shù)。 6）大規(guī)模數(shù)據(jù) 大規(guī)模數(shù)據(jù) 1）宏觀上優(yōu)化 宏觀上優(yōu)化 狀態(tài)劃分能否降維