枚舉、搜索和動態(tài)規(guī)劃經(jīng)典試題精講

1、枚舉、搜索和動態(tài)規(guī)劃經(jīng)典試題精講枚舉 所謂枚舉法,指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗(yàn)條件判定哪些是無用的,哪些是有用的.能使命題成立,即為其解。一般思路：對命題建立正確的數(shù)學(xué)模型；根據(jù)命題確定的數(shù)學(xué)模型中各變量的變化范圍（即可能解的范圍）；利用循環(huán)語句、條件判斷語句逐步求解或證明；枚舉法的特點(diǎn)是算法簡單，但有時運(yùn)算量大。對于可能確定解的值域又一時找不到其他更好的算法時可以采用枚舉法。 枚舉法求解的問題必須滿足兩個條件： 可預(yù)先確定每個狀態(tài)的元素個數(shù)n； 狀態(tài)元素a1，a2，an的可能值為一個連續(xù)的值域。設(shè)ai1狀態(tài)元素ai的最小值；aik狀態(tài)元素ai的最大值(1in)即a1

2、1a1a1k , a21a2a2k ,ai1aiaik , , an1anankfor a1a11 to a1k do fo a2a21 to a2k do for anan1 to ank do if 狀態(tài)(a1，ai，an)滿足檢驗(yàn)條件 then 輸出問題的解；枚舉算法的優(yōu)化枚舉算法的時間復(fù)雜度可以用狀態(tài)總數(shù)*考察單個狀態(tài)的耗時來表示，因此優(yōu)化主要是減少狀態(tài)總數(shù)（即減少枚舉變量和枚舉變量的值域）降低單個狀態(tài)的考察代價優(yōu)化過程從幾個方面考慮。具體講提取有效信息減少重復(fù)計(jì)算將原問題化為更小的問題根據(jù)問題的性質(zhì)進(jìn)行截枝引進(jìn)其他算法偵探推理 (NOIP2003-2)證詞中出現(xiàn)的其他話，都不列入邏輯

3、推理的內(nèi)容。明明所知道的是，他的同學(xué)中有N個人始終說假話，其余的人始終說真話?，F(xiàn)在，明明需要你幫助他從他同學(xué)的話中推斷出誰是真正的兇手，請記住，兇手只有一個！要求：判斷誰是罪犯？分析這道題的關(guān)鍵點(diǎn)是“如何能夠快速正確實(shí)現(xiàn)出來” ，事實(shí)上這道題對編碼能力的要求要大于對算法本身的要求。由于這道題的數(shù)據(jù)范圍并不是很大，但需要進(jìn)行“字符串處理”這種比較麻煩的工作，因此在比賽時就可以采用效率低一些的枚舉算法來換取編碼上的簡單。推薦的算法分為兩步：1預(yù)處理每個人的每一句話，并把它們分類處理；2枚舉罪犯和當(dāng)前星期幾，找出所有可能發(fā)生的情況。下面我們來逐步細(xì)化一下每一步的算法，對于第一步，我們希望的是把一些雜

4、亂的不好處理的“字符串信息”轉(zhuǎn)化為相對比較好處理的信息。為此，我們可以通過把“信息”進(jìn)行分類的方法使得對于每一類信息，更加方便的處理（即我們可以用一個或者幾個變量來表示），由題目描述可以發(fā)現(xiàn)語句可分為三類：分析1指明i是否是罪犯的語句；2指明今天是星期d的語句；3沒有意義的語句(不符合格式要求)。我們必須要說明的是任何不符合格式要求的語句都將被劃分到第三類中去，這樣在處理每個語句的時候就必須要考慮該語句是否符合格式要求，通過以上的處理，我們對于每一個語句用幾個變量就可以表示了。對于第二步的細(xì)化，我們在枚舉完罪犯和當(dāng)前星期幾之后，就可以比較方便的判斷每一句話的真?zhèn)瘟?，這樣我們再根據(jù)每個人所說的話

5、把人進(jìn)行分類。1沒說任何一句有意義的話；2只說真話；3只說假話；4既說真話也說假話。分析需要注意的是，對于第一類人我們既可以把他當(dāng)成說真話的，也可以把他當(dāng)成說假話的，而如果第四類人存在的話，那么從他本身就可以推出矛盾了。最后，如果對于罪犯i存在一個d使得當(dāng)前情況是可能的，我們就說i就是可能的罪犯。時間效率O(MP|Day|) （其中Day=Sunday，Monday, Tuesday, Wednesday, Thursday, Friday, Saturday）優(yōu)化我們可以發(fā)現(xiàn)在對罪犯和當(dāng)前星期幾進(jìn)行“雙重枚舉”時，進(jìn)行了很多重復(fù)的操作，于是我們想到，能不能不枚舉是當(dāng)前星期幾？這樣我們把這類語

6、句與判斷罪犯的語句分離，可以先由判斷罪犯的語句中確定一部分人肯定說真話，一部分人肯定說假話，剩下的一部分人就要根據(jù)他所說的當(dāng)前星期幾的語句來判斷了，首先我們假設(shè)所有人判斷星期的語句不自相矛盾，這樣每個人將在判斷這類問題里面至多有一個答案，我們便可以統(tǒng)計(jì)判斷當(dāng)前是星期d的總?cè)藬?shù)，于是改進(jìn)后的算法對于每一個可能的罪犯，先用O(p)的時間處理所有的話，再用O(|Day|)的時間枚舉星期幾。這樣，改進(jìn)后算法的復(fù)雜度就是O(m(p+|Day|)。那么我們可不可以再進(jìn)一步，把算法優(yōu)化到線性？這里面可以比較明確地告訴大家，是可以做到的，具體的算法類似于上面的按照語句的種類分離語句，只是分離得更細(xì)，處理得更復(fù)

7、雜，在這里就不做贅述，留給大家思考?，F(xiàn)有一個棱長為n的立方體，可以分成n3個1*1*1的單位立方體。每個單位立方體都有一個整數(shù)值。n3個單位立方體的數(shù)和不會超過longint范圍?，F(xiàn)在要求在這個立方體找到一個包含完整單位立方體的長方體，使得該長方體內(nèi)所有單位立方體的數(shù)和最大。輸入： n(1n20)；n個n*n的數(shù)字矩陣，每個數(shù)字矩陣代表一層，每個數(shù)字代表一個單位立方體的整數(shù)值，-999單位立方體的整數(shù)值999輸出：長方體的數(shù)和1、“直譯”枚舉過程for x11 to n do 枚舉所有可能的平面 for x21 to n do for y11 to n do for y21 to n do f

8、or z11 to n do 枚舉所有可能的上平面和下底面 for z21 to n do 考察狀態(tài)（x1，y1，z1，x2，y2，z2）；立方體問題考察狀態(tài)（x1，y1，z1，x2，y2，z2）的任務(wù)是計(jì)算長方體的體積，并調(diào)整最優(yōu)解。設(shè)map為立方體對應(yīng)的三維矩陣；sum為當(dāng)前長方體的體積；best為最優(yōu)解?？疾爝^程如下 sum0； for xx1 to x2 do 計(jì)算長方體的體積 for yy1 to y2 do for zz1 to z2 do sumsum+mapx，y，z； 調(diào)整最優(yōu)解 if sumbest then bestsum；這個算法相當(dāng)粗糙，枚舉狀態(tài)的費(fèi)用為O（n9） 2

9、、從減少重復(fù)計(jì)算入手記錄先前考察的結(jié)果。在統(tǒng)計(jì)長方體2時，只要將長方體1的統(tǒng)計(jì)結(jié)果加上長方體3就可以了，而不必按上述算法那樣重新進(jìn)行計(jì)算。 for x11 to n do 枚舉所有可能的水平面 for x21 to n do for y11 to n do for y21 to n do for z11 to n do 枚舉上平面的z軸坐標(biāo) begin sum0； 長方體的體積初始化 for z21 to n do 枚舉下底面的z軸坐標(biāo) 考察狀態(tài)（x1，y1，z1，x2，y2，z2）； end；for考察過程改為 for xx1 to x2 do 計(jì)算長方體的體積 for yy1 to y2

10、do sumsum+mapx，y，z2； if sumbest then bestsum； 調(diào)整最優(yōu)解由于利用了計(jì)算出的結(jié)果，整個算法的時間復(fù)雜度降為O（n8）。3、提取恰當(dāng)?shù)男畔⑸鲜隹疾鞂?shí)際上求出z軸坐標(biāo)為z2的平面中矩形（x1，y1，x2，y2）的數(shù)和。我們將這個數(shù)和記為value(a) value(A)=value(ABCD)+value(B)-value(BC)-value(BD)這就啟發(fā)我們用另一種方法表示立方體的信息：設(shè)recx，y，z表示z軸坐標(biāo)為z的水平面中矩形（1，1，x，y）的數(shù)和。z軸坐標(biāo)為z的水平面中左上角為（x1，y1）、右下角為（x2，y2）的矩陣的數(shù)和為recx2

11、，y2，z+ recx1，y1，z-recx2，y1，z-recx1，y2，zRec數(shù)組可以在輸入數(shù)據(jù)的同時計(jì)算fillchar(rec，size(rec)，0)；rec數(shù)組初始化for z1 to n do 逐層輸入信息 for x1 to n do 逐行輸入z平面的信息 begin for y1 to n do 逐列輸入z平面上x行的信息begin read(mapx，y，z)； 輸入z平面上（x,y）中的數(shù) if (x=1)and(y=1) 計(jì)算z平面上以（1，1）為左上角、（x,y）為右下角的矩形的數(shù)和then rec1，1，zmap1，1，zelse if y=1 then recx

12、，y，zrecx-1，n，z+mapx，y，z else recx，y，zrecx，y-1，z+mapx，y，z； end；for readln； end；for這樣，考察過程就可以改為 sumsum+recx2，y2，z2+recx1，y1，z2-recx2，y1，z2-recx1，y2，z2； if sumbest then bestsum；時間復(fù)雜度降為O（n6）。如果長方體a的數(shù)和是負(fù)數(shù)，則長方體a的計(jì)算結(jié)果廢棄，考察長方體b-a。因?yàn)殚L方體b的數(shù)和=長方體b-a的數(shù)和+長方體a的數(shù)和，由于長方體a的數(shù)和為負(fù)，長方體b-a的數(shù)和一定大于等于長方體b的數(shù)和。由此可見，在累計(jì)長方體數(shù)和的時

13、候，只要由上而下地枚舉長方體下底面的z軸坐標(biāo)即可。設(shè)total(z)以z軸坐標(biāo)為z的平面為下底面的長方體的最大數(shù)和for x11 to n do 枚舉所有可能的子平面 for x21 to n do for y11 to n do for y21 to n do begin total0；長方體以(x1,y1)為左上角,(x2,y2)為右下角）的最大數(shù)和初始化 for z1 to n do 枚舉長方體b下底面的z軸坐標(biāo) begin totalmaxtotal，0+ recx2，y2，z+ recx1-1，y1-1，z-recx2，y1-1，z-recx-1-1，y2，z； 計(jì)算以z為下底面的長

14、方體b的最大數(shù)和 if total best then besttotal； 調(diào)整最優(yōu)解 end；for end；for這一改進(jìn)使得考察的狀態(tài)整數(shù)降為O(n5) 子串給定一個由自然數(shù)串聯(lián)而成的無限數(shù)列（母串）求任意一個長度不超過200的數(shù)列（子串）在其中最早出現(xiàn)的位置。分析：首先，由于母串可無限擴(kuò)充，顯然我們不可能把它全部生成出來。 如果邊生成母串，邊判斷所生成的數(shù)串是否包含給定的子串，即使是使用字符串處理中高效的KMP算法，耗費(fèi)的工作量也是巨大的。1121314先枚舉第1位1自然數(shù)1之后為2,3,母串中形如123與子串從第2位開始不符枚舉前2位11自然數(shù)11之后為12,13母串中形如1112

15、13與子串從第3位開始不符考慮第2位開始12自然數(shù)12之前為11,末位與子串第1位相同，之后為13,14,母串中形如1314與子串匹配！如何優(yōu)化呢？較好的方法是另辟蹊徑：剛才我們枚舉的是母串的每一位，不妨換一個角度，從子串著手。先來觀察一些片斷： 11213141516很自然得到算法：枚舉子串所包含第一個完整的數(shù)a的位數(shù)La。假設(shè)a在母串的第k位出現(xiàn)（k=La）判斷接下來由a生成的序列是否與子串吻合。如果吻合，則最優(yōu)解的判斷：(1) LaAns_k4跟據(jù)Ans_a及Ans_k計(jì)算出位數(shù)總時間復(fù)雜度約為O(n3)，與之前的不可估量相比有了本質(zhì)性提高。第4步可通過多種途徑求得，這里不作介紹。由于其

16、中牽涉到許多高精度的計(jì)算及字符串處理，要求我們細(xì)致認(rèn)真。小結(jié)充分挖掘題目特性是解決本題的關(guān)鍵。得以使枚舉這類看似低效率的方法得到較好的運(yùn)用。同時細(xì)致全面的考慮問題也是必不可少的。寬度優(yōu)先遍歷算法框架從某個未被訪問的頂點(diǎn)v出發(fā),依次訪問v的各個未曾訪問過的鄰接點(diǎn).然后分別從這些鄰接點(diǎn)出發(fā)廣度優(yōu)先搜索遍歷,直到所有已被訪問的鄰接點(diǎn)都被訪問到.PROC bfs(v);Visite(v); vistedv:=true;Iniqueue(q); enqueue(q,v);While not empty(q) do v:=dlqueue(q);w:=FIRSTADJ(v);While w0 do if n

17、ot visitedw then visite(w);visitedw:=true; enqueue(q,w) w:=NEXTADJ(v,w); ENDP神經(jīng)網(wǎng)絡(luò)(NOIP2003-1) 在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱為神經(jīng)元，而且兩個神經(jīng)元之間至多有一條邊相連，下圖是一個神經(jīng)元的例子： 圖中，X1X3是信息輸入渠道，Y1Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個內(nèi)在參數(shù)。 神經(jīng)元按一定的順序排列，構(gòu)成整個神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從

18、上一層神經(jīng)元接受信息。 神經(jīng)網(wǎng)絡(luò)蘭蘭規(guī)定，Ci服從公式：（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目） 公式中的Wji（可能為負(fù)值）表示連接j號神經(jīng)元和 i號神經(jīng)元的邊的權(quán)值。當(dāng) Ci大于0時，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時，下一秒它會向其他神經(jīng)元傳送信號，信號的強(qiáng)度為Ci。 如此在輸入層神經(jīng)元被激發(fā)之后，整個網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿酉逻M(jìn)行運(yùn)作?，F(xiàn)在，給定一個神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（Ci），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)?！据斎敫袷健?第一行是兩個整數(shù)n（1n20）和p。接下來n行，每行兩個整數(shù)，第i1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的

19、神經(jīng)元開始時狀態(tài)必然為0。再下面P行，每行由兩個整數(shù)i，j及一個整數(shù)Wij，表示連接神經(jīng)元i、j的邊權(quán)值為Wij?！据敵龈袷健?輸出包含若干行，每行有兩個整數(shù)，分別對應(yīng)一個神經(jīng)元的編號，及其最后的狀態(tài)，兩個整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號由小到大順序輸出！ 若輸出層的神經(jīng)元最后狀態(tài)均為 0，則輸出 NULL。分析 理解問題的第一步就是認(rèn)真“讀題”。那么我們先來看一看這個題目涉及的問題。研究一下題目中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：1圖中所有的節(jié)點(diǎn)都有一個確定的等級，我們記作Level(i)2圖中所有的邊都是有向的，并且從Level值為i-1的節(jié)點(diǎn)指向L

20、evel值為i的節(jié)點(diǎn) 我們不妨將其抽象為“階段圖”。更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無環(huán)的，這樣我們可以通過拓?fù)渑判騺淼玫狡谕奶幚砉?jié)點(diǎn)的順序。可行算法 由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級都是相鄰的，因此就可以設(shè)計(jì)出一個基于寬度優(yōu)先搜索（即BFS）的算法：1初始時將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；2取出隊(duì)列中的一個元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的邊的目標(biāo)節(jié)點(diǎn)；3如果隊(duì)列非空，則轉(zhuǎn)向2；4輸出輸出層中所有滿足條件的節(jié)點(diǎn)。但是由于本題在問題描述中并沒有明確的給出判斷一個節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個過程即便是真實(shí)數(shù)據(jù)沒有這

21、樣出也是要有的），下面給出的更一般的算法可能會更好的跳過這些邊界情況。1對原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍?按照拓?fù)漤樞蛱幚砻恳粋€節(jié)點(diǎn)；3輸出輸出層中所有滿足條件的節(jié)點(diǎn)。Amazing Robots: IOI2003已知條件： 迷宮 i（i=1,2） （每個不會大于20*20） 守衛(wèi) Gi（0=Gi=10） （守衛(wèi)循環(huán)移動進(jìn)行執(zhí)勤） （守衛(wèi)巡邏的方格數(shù)（2.4）求： 兩個機(jī)器人都離開迷宮所用的最少指令數(shù)目 和離開制指令序列（10000 步以內(nèi)）。每一步可以發(fā)出的命令可以是N, E, S, W中的一種，有4種選擇。對每一步具體發(fā)出哪個命令，直接搜索。假設(shè)最后結(jié)果是T。（也就是最少出宮時間）時間

22、復(fù)雜度是O(4T)這種方法時間復(fù)雜度太高，絕對不可行!5*4和4*4的迷宮第一個機(jī)器人的位置是(2,2)第二個機(jī)器人的位置是(3,2)當(dāng)前時間是0。狀態(tài)(2,2),(3,2),0)狀態(tài)表示： （第一個機(jī)器人位置，第二個機(jī)器認(rèn)位置，時間）E(2,2),(3,2),0)(2,3),(3,3),1)時間已知，則所有Guard的位置可知。Guard、Robot的位置均已知，所以狀態(tài)可以轉(zhuǎn)移0時刻1時刻2時刻3時刻0時刻和2時刻是一樣的1時刻和3時刻是一樣的。稍加分析：此Guard循環(huán)以2為周期循環(huán)。狀態(tài)轉(zhuǎn)移，需要的信息是：Robot位置，Guard位置。Position of Robot1, 2是的作

23、用就是記錄Robot位置。Time的作用就是為了計(jì)算Guard的位置狀態(tài)：(position of Robot1, position of Robot2, Time)Time=10000，這是狀態(tài)數(shù)過多的罪魁禍?zhǔn)?！題目說：Guard巡邏經(jīng)過的格子數(shù)只可能是2, 3, 4。也就是說機(jī)器人巡邏周期只能是2, 4, 6。2, 4, 6=12，所以第0時刻、12時刻、24時刻Guard的狀態(tài)完全相同。12可以看作Guard的周期。Time只要記錄當(dāng)前是第幾個周期。因?yàn)橹芷诖_定了，Guard的位置也完全確定了！ 0=Time=11狀態(tài)數(shù)(n*n)*(n*n)*12=12n4。用BFS算法，標(biāo)志數(shù)組判重。

24、時間復(fù)雜度O(12n4)。n=20完全可以承受 -深度優(yōu)先遍歷從某個未被訪問的頂點(diǎn)v出發(fā),深度優(yōu)先遍歷圖,直到和v有路徑的頂點(diǎn)都訪問到.PROC dfs(v); visite(v);visitedv=true; w:=FIRSTADJ(v); while w0 do if not visitedw then dfs(w) w:=NEXTADJ(v,w); ENDP討論:蟲食算問題給出一個N進(jìn)制的蟲食算式，相同的字母代表相同的數(shù)字，不同的字母代表不同的數(shù)字。要求求出滿足這個算式的唯一一組解，也就是字母和數(shù)字的一一對應(yīng)關(guān)系.解決方案1:要求一一對應(yīng)的關(guān)系，就可以枚舉這些一一對應(yīng)的關(guān)系，找出符合的一

25、項(xiàng)。這樣，關(guān)系總數(shù)有O(N!)個，最壞情況下必須枚舉所有的關(guān)系，并且加以判斷，復(fù)雜度高達(dá)O(N*N!)！解決方案2:大體上，從算式最后一位開始模擬運(yùn)算情況，當(dāng)可遞推時遞推，不可遞推則枚舉。對于一豎列，先處理兩個加數(shù)，當(dāng)遇到的字母的值不確定時，則枚舉當(dāng)前位（注意與前面的情況判重）；否則不作為處理和，當(dāng)遇到的字母的值不確定時,可從加數(shù)部分確定的值來確定（注意與前面的情況判重和進(jìn)位）；否則看加數(shù)部分確定的值是否能得到和部分（注意進(jìn)位）。引出矛盾就回溯。如題目的樣例：5ABCEDBDACEEBBAA它最后一位的情況是(D+E) mod N=A, 對于最后一位只要枚舉D,E的情況；A 則可以由D,E的值

26、遞推而來。對于倒2位, (E+C+最后一位進(jìn)位) mod N=A ；E的值可以用前面的結(jié)果；枚舉C；判斷A是否為(D+C+最后一位進(jìn)位) mod N雖然復(fù)雜度還是O(N!)，但這種方法限制很多（相當(dāng)于剪枝）。 解決方案3: 觀察題目的條件已經(jīng)限制得很苛刻：N個變量，每個至少出現(xiàn)一次；而且正好一共有N位的算式。這樣就構(gòu)成了解方程的動機(jī)。這N個變量的對應(yīng)N個未知量，有N位的算式對應(yīng)N個方程；N個未知量，N個方程，正好可以得到唯一解。這里要注意，對解的要求很嚴(yán)格：必須是0至N-1的每個整數(shù)都正好出現(xiàn)一次。但對每位式子的進(jìn)位關(guān)系并不清楚，而進(jìn)位關(guān)系正好影響了方程的常數(shù)項(xiàng)。枚舉每位是否進(jìn)位。用時O(2n

27、), (因?yàn)槭孜徊豢赡苓M(jìn)位，無須枚舉)。然后，用高斯消元法來解方程?？梢栽诿杜e之前先解出方程，枚舉的時候再把參數(shù)帶入。帶入求解的復(fù)雜度是O(n2) 。解決方案4:在解決方案3的基礎(chǔ)上，我們可以對進(jìn)位的枚舉剪枝。觀察這個豎列：A+B=C，若無進(jìn)位則有A=C且BC且B=C.若能推導(dǎo)出A=A （A,B為任何不相等字母），則當(dāng)前的枚舉不可行?？捎眠f歸枚舉，從后向前枚舉，處理一個豎列時則加上2個不等式，看是否矛盾。數(shù)據(jù)結(jié)構(gòu)用鄰接矩陣。（規(guī)定A=B，再有向圖中有邊）。若加進(jìn)不等式A=B ，要加入所有x(x=A) =y(B=y)，枚舉x,y用O(n2)得時間。再判斷是否有x=y.森林中的果樹森林中長著一種奇

28、怪的果樹,在每個分叉處生長著果實(shí)，小蟲Nileh和Nixed的食物就是這些果實(shí)！他們準(zhǔn)備把果樹分成兩部分，每個蟲蟲得到各自的一部分，而分果樹的方法就是選擇一個分叉點(diǎn)，蟲蟲將他們咬斷（自然分叉點(diǎn)上的果實(shí)也被扔掉了），這樣果樹就變成了兩個部分：分叉點(diǎn)上面的部分和分叉點(diǎn)下面的部分。 （注意,每個部分不一定是連在一起的）,比如對于右邊這顆果樹，如果他們咬掉藍(lán)色的果子，那么就被分為紅色和黃色的兩個部分。 被咬掉的果子會被浪費(fèi)，他們想盡可能的減少浪費(fèi)，于是蟲蟲給每個果子一個美味值，對于每個果子，請計(jì)算如果咬掉這個果子，它上面部分、下面部分和從樹根到這個分叉點(diǎn)的路徑中比這個果子更美味的果子各有多少個。 分析

29、圖例算法考慮一個點(diǎn)P，對樹進(jìn)行從左到右的深度優(yōu)先遍歷，那么在A,D部分的點(diǎn)會在P之前被訪問，B,C在之后被訪問。同理，從右到左深度優(yōu)先遍歷，那么B,D先被訪問，A,C后被訪問。對于求出的這兩個序列，可以用nlogn求出序列中每個點(diǎn)之前有多少個點(diǎn)比它大。也就是我們可以求出每個點(diǎn)的Fa+Fd，F(xiàn)b+Fd（Fi表示在i部分中有多少點(diǎn)比固定點(diǎn)大）Fd可以用一遍深度優(yōu)先遍歷求出。最長上升序列 設(shè)有整數(shù)序列b1,b2,b3,bm ，若存在下標(biāo)i1i2i3in，且bi1bi2bi3 bin，則稱 b1,b2,b3,bm中有長度為n的上升序列bi1 , bi2 ,bi3 ,bin 。求序列b1,b2,b3,b

30、m的最大上升長度n,以及所有長度為n的最大上升子序列個數(shù)t輸入：整數(shù)序列。輸出：n,t分析（1）設(shè)f(i)為前i個數(shù)中的最大不下降序列長度 , 則f(i)=maxf(j)+1 (1=ji=m, bjbi)邊界為F(1)=1(2)設(shè)t(i)為前i個數(shù)中最長不下降序列的個數(shù),則t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)-1) 初始為t(i)=1當(dāng)f(i)=n時，將t(i)累加舉例： 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2答案：f=7時，邊界為t=4進(jìn)一步(3)求本質(zhì)不同的最長不下降序列個數(shù)

31、有多少個？ 如：1 2 3 4 6 5 8 10 9 有， 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8 9 都是本質(zhì)不同的。 但對于 1 2 2 3 3 5 4 f 1 2 2 3 3 5 4 t 1 1 1 2 2 4 4 答案有8個，其中4個1 2 3 5 ，4個1 2 3 4改進(jìn)算法上例顯然對于相兩個相同的數(shù)，重復(fù)算了多次因此，我們對算法進(jìn)行改進(jìn)：對原序列按b從小到大（當(dāng)bi=bj時按F從大到?。┡判颍鲈O(shè)Order(i)記錄新序列中的i個數(shù)在原序列中的位置?？梢?，求t(i)時，當(dāng)f(j)=f(j+1),b(j)

32、=b(j+1)且Order(j+1)Order(i)時，便不累加t(j)。這樣就避免了重復(fù)。 上述算法的時間復(fù)雜度為O(n2) 合唱隊(duì)形(NOIP2005-3)給出N個人，第i個人的高度為Ai,現(xiàn)在要求找出一個對形,使得從某個人開始,前面的人都呈遞增的順序排列,后面的人呈遞減順序排列找出最長的該隊(duì)列.解法動態(tài)規(guī)劃：枚舉中間最高的一個人，接著對它的左邊求最長上升序列（注意序列中最高的同學(xué)不應(yīng)高過基準(zhǔn)），對右邊求最長下降序列（同樣的，序列中最高的同學(xué)不應(yīng)高過基準(zhǔn)）。時間復(fù)雜度為O(n2)，算法實(shí)現(xiàn)起來也很簡單。接著對這個算法進(jìn)行分析，我們不難發(fā)現(xiàn)，假如還是基于枚舉一個同學(xué)的話，設(shè)Incsqi表示了

33、1 - i的最長上升序列，Decsqi表示了i - n的最長下降序列，那么，Currenti = Incsqi + Decsqi - 1（兩個數(shù)組中i被重復(fù)計(jì)算了）那么，我們只需要先求好最長上升和下降序列，然后枚舉中間最高的同學(xué)就可以了。優(yōu)化求最長上升序列的經(jīng)典狀態(tài)轉(zhuǎn)移方程為：opti = maxoptj+1, 其中ijlisti我們對狀態(tài)轉(zhuǎn)移方程稍微做一些修改：opti = maxopt(i+1), minj | recj=listi recj 記錄當(dāng)前不下降序列的最小值很明顯可以看出，在opti的尋找j的過程當(dāng)中，查詢序列是單調(diào)的，于是可以用二分法，就十分巧妙地在logn的時間內(nèi)找到指定的

34、j，而問題的總體復(fù)雜度為O(nlogn)。這樣，這個問題的算法效率就得到了大幅度的提升，即便n是106，也可以輕松應(yīng)對。二叉堆定義n個元素的序列k1,k2,kn，當(dāng)且僅當(dāng)滿足 ki=k2i 并且 ki =k2i 并且 ki = k2i+1 二叉堆肯定是一顆完全二叉樹堆的構(gòu)造第一步,構(gòu)造一個初始堆第二步,逐步調(diào)整該堆,使它符合堆的性質(zhì)堆排序算法PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=rk.key;finish:=false t:=rk; while (j=m) and not finish do if (jrj+1.ke

35、y) then j:=j+1; If x=rj.key then finish:=true Else ri:=rj; i:=j; j:=2*I ri:=tendPPROC heapsort(var r:listtype);For i:=n/2 downto 1 shift(r,I,n);For i:=n downto 2 do r1與ri交換; shift(r,1,i-1) endP合并果子把合成堆后的每堆的果子仍然看成相對獨(dú)立的，那么定義timesi等于第i堆果子被合并的次數(shù)，ai為第i堆數(shù)字權(quán)值。則 Totalcost= ，目標(biāo)求得是 minTotalcost。建立一棵二叉樹，每堆果子分別

36、為該樹的葉節(jié)點(diǎn)，一種二叉樹形態(tài)對應(yīng)一種合并方案（2堆果子合并則有共同父結(jié)點(diǎn)），所以該方案的Totalcost =depthi*vi ，i是葉節(jié)點(diǎn)。解法是每次取出最小的兩個節(jié)點(diǎn)，并從節(jié)點(diǎn)集合中刪除，然后合并這兩點(diǎn)后再加入節(jié)點(diǎn)集合；重復(fù)，直到只剩一個節(jié)點(diǎn)； 由于每次要取出最小的兩個節(jié)點(diǎn)。一般做法是每更新一次集合，重新排序，時間是O(n2)。由于n=10000，不得不采用數(shù)據(jù)結(jié)構(gòu)-堆進(jìn)行優(yōu)化。 解決方案方法或要點(diǎn)時間復(fù)雜度可過數(shù)據(jù)解決方案1一般做法30%-50%解決方案2堆100%最大子序和問題描述 輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的長度不超過M的子序列，使得這個序列的

37、和最大。最大子序和例如： 序列 1， -3， 5， 1， -2， 3當(dāng)M=2或3時S=5+1=6當(dāng)M=4時S=5+1+(-2)+3=7數(shù)據(jù)范圍: 50%的數(shù)據(jù)N,M=1000 100%的數(shù)據(jù)N,M=20000一個簡化的問題序列的最大連續(xù)和 輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的子序列，使得這個序列的和最大。 和原問題相比沒有M這個序列長度的限制！分析： 設(shè) F(i)表示以第i個數(shù)結(jié)尾的最大連續(xù)和 以第i個數(shù)結(jié)尾的最大連續(xù)和序列，可能存在兩種選擇： 情形一：只包含Ai 情形二：包含Ai和以Ai-1結(jié)尾的最大連續(xù)和序列動態(tài)規(guī)劃：轉(zhuǎn)移方程： F(i)=maxAi , F(i

38、-1)+Ai邊界：F(1)=A1要求的結(jié)果為maxF(i)|1=i=n該算法的時間復(fù)雜度為O(n)一個簡化的問題例一 算法一枚舉設(shè) F(i)為以Ai結(jié)尾長度不超過M的最大子序和 對于每個F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時間復(fù)雜度為O(n2)原問題初步分析簡化方程 用一個二叉堆來維護(hù)S(i-k)，每次求F(i)之前的操作如下：算法二堆求F(i-1)時，求minS(i-m-1), ,S(i-2)求F(i)時， 求minS(i-m),S(i-1)在堆中刪除元素S(i-m-1)，插入元素S(i-1).復(fù)雜度O(2log2n)從堆中取出當(dāng)前最小值.復(fù)雜度O(1) 所以計(jì)算

39、的總復(fù)雜度為O(nlog2n)隊(duì)列優(yōu)化 在算法二中，考慮用隊(duì)列來維護(hù)決策值S(i-k)。每次只需要在隊(duì)首刪掉S(i-m-1)，在隊(duì)尾添加S(i-1) 。但是取最小值操作還是需要O(n)時間復(fù)雜度的掃描。 考察在添加S(i-1)的時候，設(shè)現(xiàn)在隊(duì)尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出隊(duì)。若此時S(i-1)=S(k)，則S(k)這個決策永遠(yuǎn)不會在以后用到，可以將S(k)從隊(duì)尾刪除掉（此時隊(duì)列的尾部形成了一個類似棧的結(jié)構(gòu)）隊(duì)列優(yōu)化 同理，若隊(duì)列中兩個元素S(i)和S(j)，若i=S(j)，則我們可以刪掉S(i)（因?yàn)镾(i)永遠(yuǎn)不會被用到）。此時的隊(duì)列中的元素構(gòu)成了一個單

40、調(diào)遞增的序列，即：S1S2S3Sk算法三 我們來整理在求F(i)的時候，用隊(duì)列維護(hù)S(i-k)所需要的操作： 若當(dāng)前隊(duì)首元素S(x)，有x=i-m為止。 若當(dāng)前隊(duì)尾元素S(k)=S(i-1)，則S(k)出隊(duì)；直到S(k)S(i-1)為止。 在隊(duì)尾插入S(i-1) 取出隊(duì)列中的最小值，即隊(duì)首元素。算法三 由于對于求每個F(i)的時候，進(jìn)隊(duì)和出隊(duì)的元素不止一個。 但是我們可以通過分?jǐn)偡治龅弥恳粋€元素S(i)只進(jìn)隊(duì)一次、出隊(duì)一次，所以隊(duì)列維護(hù)的時間復(fù)雜度是O(n)。而每次求F(i)的時候取最小值操作的復(fù)雜度是O(1)，所以這一步的總復(fù)雜度也是O(n)。 綜上所述，該算法的總復(fù)雜度是O(n)小結(jié)

41、在本題的解決過程中，我們首先通過對于一個簡化的問題解答，得到了該類問題一般性的解決思路，隨后得到了一個O(n2)的算法 我們通過簡化方程，進(jìn)一步明確和細(xì)化了求解目標(biāo)，運(yùn)用合理的數(shù)據(jù)結(jié)構(gòu)堆，得到了一個O(nlog2n)的算法。 通過進(jìn)一步的挖掘求解目標(biāo)的內(nèi)涵，尋找內(nèi)在規(guī)律，我們得到只用線性表維護(hù)的O(n)的算法。過河(NOIP2005) 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，L（其中L是橋的長度）。坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)

42、，坐標(biāo)為L的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為L的點(diǎn)時，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)?！据斎胛募枯斎胛募牡谝恍杏幸粋€正整數(shù)L（1 = L = 109），表示獨(dú)木橋的長度。第二行有三個正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數(shù)，其中1 = S = T = 10，1 = M = 100。第三行有M個不同的正整數(shù)分別表示這M個石子在數(shù)軸上的位置（數(shù)據(jù)保證

43、橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開?！据敵鑫募枯敵鑫募话ㄒ粋€整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)?！緲永斎搿?02 3 52 3 5 6 7【樣例輸出】2【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，L = 10000；對于全部的數(shù)據(jù)，L = 109。 分析 由于不能往回跳，很容易想到用動態(tài)規(guī)劃解決這個題目。設(shè)f(i)表示跳到第i個點(diǎn)需要踩到的最少石子數(shù)，則很容易寫出動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程:時間復(fù)雜度是O(L*(T-S)，但本題的L高達(dá)109，根本無法承受! 進(jìn)一步分析我們先來考慮這樣一個問題：長度為k的一段沒有石子的獨(dú)木橋，判斷是否存在一種跳法從一端正好跳到另一端。若S=MaxK，都可以從一端正好跳到另一端。題設(shè)中1=S=T=10，經(jīng)過簡單推導(dǎo)或者程序驗(yàn)證就可以發(fā)現(xiàn)，取MaxK=100就能滿足所有區(qū)間。 于是我們可以分兩種情況討論：1. S=T時：這時候由于每一步只能按固定步長跳，所以若第i個位置上有石子并且i mod S=0那么這個石子就一定要被踩到。這是我們只需要統(tǒng)計(jì)石子的位置中哪些是S的倍數(shù)即可。復(fù)雜度O(M)2. SMaxK+2*T，我們就將這段區(qū)域縮短成長度為MaxK+2*T?？梢宰C明處理之后的最優(yōu)值和原先的最優(yōu)值相同。ab如上圖所示，白色點(diǎn)表示連續(xù)的一長段長度大于MaxK+2*T的空地，黑色點(diǎn)表示石子。設(shè)原先的最優(yōu)解中，白色