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

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

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

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

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

6、不必過(guò)于關(guān)注。其特點(diǎn)是:在平面或立體內(nèi),以點(diǎn)坐標(biāo)或相應(yīng)矩形為狀態(tài)。典型問(wèn)題有棋盤(pán)分割和奶牛浴場(chǎng)。特別留意:1.此類(lèi)題目往往根據(jù)幾何關(guān)系或數(shù)學(xué)知識(shí)推斷出轉(zhuǎn)移方程。8集合狀態(tài)類(lèi)這種類(lèi)型也不多見(jiàn),但特點(diǎn)很突出。它往往具有多個(gè)狀態(tài)維數(shù),有時(shí)多達(dá)5,6個(gè),而且決策與若干個(gè)狀態(tài)組成一個(gè)整體,修改最值時(shí)一同更新。典型例題有購(gòu)物和快餐問(wèn)題。特別留意:1.確定使用此類(lèi)DP后,大膽增設(shè)狀態(tài)維數(shù)。2.要找出切實(shí)可行的轉(zhuǎn)移方程和算法實(shí)現(xiàn)方式。9字符串類(lèi)特別留意:1.要確定最優(yōu)解的狀態(tài)的所有可能性。2.多數(shù)時(shí)候此類(lèi)問(wèn)題還是屬于線(xiàn)性類(lèi)問(wèn)題,需要結(jié)合線(xiàn)性類(lèi)的特點(diǎn)設(shè)計(jì)算法。3.可留意一下KMP算法。4.可留意一下回文字一類(lèi)題

7、目。3.NOIP可能會(huì)給模型增加的難度1非線(xiàn)性數(shù)據(jù)類(lèi)型在數(shù)據(jù)類(lèi)型方面,NOIP最可能增添的難度是出環(huán)狀和樹(shù)狀。1樹(shù)狀對(duì)于樹(shù)狀,我們通常可以用樹(shù)型DP解決。需留意的是,有些看似樹(shù)型DP的題,其實(shí)可能是區(qū)間類(lèi)DP,如03年的加分二叉樹(shù)。另外,樹(shù)的輸入方式有很多種,我們必須熟悉如何恰當(dāng)保存樹(shù)的數(shù)據(jù),否則即便會(huì)做DP也拿不了分。2環(huán)狀對(duì)于環(huán)狀,我們有兩種處理方法將其破壞成鏈:1.確定某結(jié)點(diǎn)為起點(diǎn),枚舉該結(jié)點(diǎn)狀態(tài),每次枚舉后DP求解,記錄起點(diǎn)為該狀態(tài)下得到的最優(yōu)解。最后將各種可能的最優(yōu)解篩選出問(wèn)題的最優(yōu)解。此類(lèi)方法適用于線(xiàn)性DP和路徑型DP。2.對(duì)于長(zhǎng)度為n的環(huán),任意選取一點(diǎn)為起點(diǎn),由起點(diǎn)開(kāi)始得到一條長(zhǎng)

8、度為n的鏈,將前面n-1長(zhǎng)度的鏈復(fù)制并轉(zhuǎn)移到鏈的末端,相當(dāng)于將兩條同樣的鏈?zhǔn)孜蚕嘟?。由?環(huán)的任意一種單向遍歷方式都可以在這個(gè)長(zhǎng)度為2n-1的鏈中實(shí)現(xiàn)。此類(lèi)方法適用于區(qū)間類(lèi)DP。從本質(zhì)上講,這兩種處理方式是完全一樣的,既枚舉起點(diǎn)的位置或狀態(tài),利用DP求解。需要留意的是,這種條件下的最優(yōu)值的位置往往要特別考慮的。2結(jié)合其他算法1貪心DP和貪心結(jié)合的例子很常見(jiàn),有以下兩種:1.通過(guò)貪心確定轉(zhuǎn)移方程,也可以作為預(yù)處理部分。例題為郵局。2.通過(guò)貪心確定最優(yōu)解的上限或下限,從而減少循環(huán)量,在大規(guī)模數(shù)據(jù)時(shí)很有效。例題為快餐問(wèn)題。2搜索搜索和DP的結(jié)合,可以體現(xiàn)在兩方面:1.記憶化搜索所謂“記憶化搜索”就是

9、在傳統(tǒng)的搜索過(guò)程中,加入DP的“保留子問(wèn)題最優(yōu)解”思想,提高時(shí)間效率。從框架上講,還是搜索算法,這里不作討論。2.搜索中的局部進(jìn)行DP求解在搜索過(guò)程中,某個(gè)局部可能用到DP進(jìn)行求解。例題為郵票面值設(shè)計(jì)。3字符串處理、高精度、排序、求質(zhì)數(shù)等這幾樣都是基礎(chǔ)算法,可作為DP的預(yù)處理,這里不多做敘述。3提出其他任務(wù)1輸出最優(yōu)方案這是很常見(jiàn)的一種題目要求,它不僅要求我們求出最優(yōu)值的大小,還要確定與之對(duì)應(yīng)的每個(gè)決策。通常有兩個(gè)方法解決:1.增添記錄每次決策的數(shù)組M。在每次做決策時(shí),M中對(duì)應(yīng)的狀態(tài)也保留一個(gè)代表該決策的值。如01背包中,某個(gè)背包取或不取,M中對(duì)應(yīng)的值為1或0。在得出最優(yōu)解后,正向遍歷M(構(gòu)建

10、隊(duì)列或逆向遍歷M(構(gòu)建棧,從而輸出最優(yōu)方案。2.一些題目的性質(zhì)決定,在得出最優(yōu)解后,可以通過(guò)貪心輸出最優(yōu)方案。如書(shū)的復(fù)制前一種方法具有普遍性,在時(shí)空允許下絕大部分DP題目適用。后一種題目在小范圍內(nèi)適用,但其編程復(fù)雜度和時(shí)空復(fù)雜度都相當(dāng)理想。2求前k優(yōu)解(方案或第k優(yōu)解(方案此問(wèn)題可通過(guò)增設(shè)狀態(tài)維數(shù)解決。在最優(yōu)解數(shù)組中增加一維p表示同樣狀態(tài)下的第p 優(yōu)解,顯然在DP過(guò)程中,只需保留每個(gè)狀態(tài)的前k優(yōu)解就足夠。在狀態(tài)轉(zhuǎn)移時(shí),算出新?tīng)顟B(tài)的前k個(gè)最優(yōu)解,依次保存。需要注意的是,每一種可以得出新?tīng)顟B(tài)的前k個(gè)最優(yōu)解的情況都要考慮到。另外,題目可能問(wèn)前k個(gè)最優(yōu)解(數(shù)字一樣時(shí)當(dāng)一種解,中間的策略不用考慮,也可能

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