搜索與動(dòng)態(tài)規(guī)劃

1、枚舉、搜索與動(dòng)態(tài)規(guī)劃試 題 精 講朱全民枚舉 所謂枚舉法所謂枚舉法,指的是從可能的解集合中一一枚舉各指的是從可能的解集合中一一枚舉各元素元素,用題目給定的檢驗(yàn)條件判定哪些是無(wú)用的用題目給定的檢驗(yàn)條件判定哪些是無(wú)用的,哪些是有用的哪些是有用的.能使命題成立能使命題成立,即為其解。一般思即為其解。一般思路：路： 對(duì)命題建立正確的數(shù)學(xué)模型；對(duì)命題建立正確的數(shù)學(xué)模型； 根據(jù)命題確定的數(shù)學(xué)模型中各變量的變化范圍根據(jù)命題確定的數(shù)學(xué)模型中各變量的變化范圍（即可能解的范圍）；（即可能解的范圍）； 利用循環(huán)語(yǔ)句、條件判斷語(yǔ)句逐步求解或證明；利用循環(huán)語(yǔ)句、條件判斷語(yǔ)句逐步求解或證明； 枚舉法的特點(diǎn)是算法簡(jiǎn)單，但有

2、時(shí)運(yùn)算量大。對(duì)枚舉法的特點(diǎn)是算法簡(jiǎn)單，但有時(shí)運(yùn)算量大。對(duì)于可能確定解的值域又一時(shí)找不到其他更好的算于可能確定解的值域又一時(shí)找不到其他更好的算法時(shí)可以采用枚舉法。法時(shí)可以采用枚舉法。 枚舉法求解的問(wèn)題必須滿(mǎn)足兩個(gè)條件：枚舉法求解的問(wèn)題必須滿(mǎn)足兩個(gè)條件： 可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n； 狀態(tài)元素狀態(tài)元素a1，a2，an的可能值為一個(gè)連續(xù)的值域。的可能值為一個(gè)連續(xù)的值域。設(shè)設(shè)ai1狀態(tài)元素狀態(tài)元素ai的最小值；的最小值；aik狀態(tài)元素狀態(tài)元素ai的最大值的最大值(1in)即即a11a1a1k , a21a2a2k ,ai1aiaik , , an1anankfor a1

3、a11 to a1k do fo a2a21 to a2k do for anan1 to ank do if 狀態(tài)狀態(tài)(a1，ai，an)滿(mǎn)足檢驗(yàn)條件滿(mǎn)足檢驗(yàn)條件 then 輸出問(wèn)題的解；輸出問(wèn)題的解；枚舉算法的優(yōu)化枚舉算法的優(yōu)化枚舉算法的時(shí)間復(fù)雜度可以用狀態(tài)總數(shù)枚舉算法的時(shí)間復(fù)雜度可以用狀態(tài)總數(shù)*考察單個(gè)狀態(tài)的耗時(shí)考察單個(gè)狀態(tài)的耗時(shí)來(lái)表示，因此優(yōu)化主要是來(lái)表示，因此優(yōu)化主要是減少狀態(tài)總數(shù)（即減少枚舉變量和枚舉變量的值域）減少狀態(tài)總數(shù)（即減少枚舉變量和枚舉變量的值域）降低單個(gè)狀態(tài)的考察代價(jià)降低單個(gè)狀態(tài)的考察代價(jià)優(yōu)化過(guò)程從幾個(gè)方面考慮。具體講優(yōu)化過(guò)程從幾個(gè)方面考慮。具體講提取有效信息提取有效信

4、息減少重復(fù)計(jì)算減少重復(fù)計(jì)算將原問(wèn)題化為更小的問(wèn)題將原問(wèn)題化為更小的問(wèn)題根據(jù)問(wèn)題的性質(zhì)進(jìn)行截枝根據(jù)問(wèn)題的性質(zhì)進(jìn)行截枝引進(jìn)其他算法引進(jìn)其他算法偵探推理偵探推理 (NOIP2003-2)證詞中出現(xiàn)的其他話(huà)，都不列入邏輯推理的內(nèi)容。證詞中出現(xiàn)的其他話(huà)，都不列入邏輯推理的內(nèi)容。明明所知道的是，他的同學(xué)中有明明所知道的是，他的同學(xué)中有N N個(gè)人始終說(shuō)假話(huà)，其余的個(gè)人始終說(shuō)假話(huà)，其余的人始終說(shuō)真話(huà)。人始終說(shuō)真話(huà)?，F(xiàn)在，明明需要你幫助他從他同學(xué)的話(huà)中推斷出誰(shuí)是真正現(xiàn)在，明明需要你幫助他從他同學(xué)的話(huà)中推斷出誰(shuí)是真正的兇手，請(qǐng)記住，的兇手，請(qǐng)記住，兇手只有一個(gè)！兇手只有一個(gè)！要求：要求：判斷誰(shuí)是罪犯？判斷誰(shuí)是罪犯

5、？分析 這道題的關(guān)鍵點(diǎn)是這道題的關(guān)鍵點(diǎn)是“如何能夠快速正確實(shí)現(xiàn)出來(lái)如何能夠快速正確實(shí)現(xiàn)出來(lái)” ” ，事實(shí)，事實(shí)上這道題對(duì)編碼能力的要求要大于對(duì)算法本身的要求。由上這道題對(duì)編碼能力的要求要大于對(duì)算法本身的要求。由于這道題的數(shù)據(jù)范圍并不是很大，但需要進(jìn)行于這道題的數(shù)據(jù)范圍并不是很大，但需要進(jìn)行“字符串處字符串處理理”這種比較麻煩的工作，因此在比賽時(shí)就可以采用效率這種比較麻煩的工作，因此在比賽時(shí)就可以采用效率低一些的枚舉算法來(lái)?yè)Q取編碼上的簡(jiǎn)單。低一些的枚舉算法來(lái)?yè)Q取編碼上的簡(jiǎn)單。 推薦的算法分為兩步：推薦的算法分為兩步：1 1預(yù)處理每個(gè)人的每一句話(huà)，并把它們分類(lèi)處理；預(yù)處理每個(gè)人的每一句話(huà)，并把它們

6、分類(lèi)處理；2 2枚舉罪犯和當(dāng)前星期幾，找出所有可能發(fā)生的情況。枚舉罪犯和當(dāng)前星期幾，找出所有可能發(fā)生的情況。 下面我們來(lái)逐步細(xì)化一下每一步的算法，對(duì)于第一步，我下面我們來(lái)逐步細(xì)化一下每一步的算法，對(duì)于第一步，我們希望的是把一些雜亂的不好處理的們希望的是把一些雜亂的不好處理的“字符串信息字符串信息”轉(zhuǎn)化轉(zhuǎn)化為相對(duì)比較好處理的信息。為此，我們可以通過(guò)把為相對(duì)比較好處理的信息。為此，我們可以通過(guò)把“信息信息”進(jìn)行分類(lèi)的方法使得對(duì)于每一類(lèi)信息，更加方便的處理進(jìn)行分類(lèi)的方法使得對(duì)于每一類(lèi)信息，更加方便的處理（即我們可以用一個(gè)或者幾個(gè)變量來(lái)表示），由題目描述（即我們可以用一個(gè)或者幾個(gè)變量來(lái)表示），由題目描

7、述可以發(fā)現(xiàn)語(yǔ)句可分為三類(lèi)：可以發(fā)現(xiàn)語(yǔ)句可分為三類(lèi)：分析1 1指明指明i i是否是罪犯的語(yǔ)句；是否是罪犯的語(yǔ)句；2 2指明今天是星期指明今天是星期d d的語(yǔ)句；的語(yǔ)句；3 3沒(méi)有意義的語(yǔ)句沒(méi)有意義的語(yǔ)句( (不符合格式要求不符合格式要求) )。 我們必須要說(shuō)明的是任何不符合格式要求的語(yǔ)句都將被劃我們必須要說(shuō)明的是任何不符合格式要求的語(yǔ)句都將被劃分到第三類(lèi)中去，這樣在處理每個(gè)語(yǔ)句的時(shí)候就必須要考分到第三類(lèi)中去，這樣在處理每個(gè)語(yǔ)句的時(shí)候就必須要考慮該語(yǔ)句是否符合格式要求，通過(guò)以上的處理，我們對(duì)于慮該語(yǔ)句是否符合格式要求，通過(guò)以上的處理，我們對(duì)于每一個(gè)語(yǔ)句用幾個(gè)變量就可以表示了。每一個(gè)語(yǔ)句用幾個(gè)變量就

8、可以表示了。 對(duì)于第二步的細(xì)化，我們?cè)诿杜e完罪犯和當(dāng)前星期幾之后，對(duì)于第二步的細(xì)化，我們?cè)诿杜e完罪犯和當(dāng)前星期幾之后，就可以比較方便的判斷每一句話(huà)的真?zhèn)瘟?，這樣我們?cè)俑涂梢员容^方便的判斷每一句話(huà)的真?zhèn)瘟耍@樣我們?cè)俑鶕?jù)每個(gè)人所說(shuō)的話(huà)把人進(jìn)行分類(lèi)。據(jù)每個(gè)人所說(shuō)的話(huà)把人進(jìn)行分類(lèi)。1 1沒(méi)說(shuō)任何一句有意義的話(huà)；沒(méi)說(shuō)任何一句有意義的話(huà)；2 2只說(shuō)真話(huà)；只說(shuō)真話(huà)；3 3只說(shuō)假話(huà)；只說(shuō)假話(huà)；4 4既說(shuō)真話(huà)也說(shuō)假話(huà)。既說(shuō)真話(huà)也說(shuō)假話(huà)。分析 需要注意的是，對(duì)于第一類(lèi)人我們既可以把他當(dāng)成說(shuō)真需要注意的是，對(duì)于第一類(lèi)人我們既可以把他當(dāng)成說(shuō)真話(huà)的，也可以把他當(dāng)成說(shuō)假話(huà)的，而如果第四類(lèi)人存在話(huà)的，也可以把他當(dāng)成說(shuō)假

9、話(huà)的，而如果第四類(lèi)人存在的話(huà)，那么從他本身就可以推出矛盾了。的話(huà)，那么從他本身就可以推出矛盾了。 最后，如果對(duì)于罪犯最后，如果對(duì)于罪犯i i存在一個(gè)存在一個(gè)d d使得當(dāng)前情況是可能的，使得當(dāng)前情況是可能的，我們就說(shuō)我們就說(shuō)i i就是可能的罪犯。就是可能的罪犯。 時(shí)間效率時(shí)間效率 O(MP|Day|) O(MP|Day|) （其中（其中Day=SundayDay=Sunday，Monday, Tuesday, Monday, Tuesday, Wednesday, Thursday, Friday, SaturdayWednesday, Thursday, Friday, Saturday）優(yōu)化

10、 我們可以發(fā)現(xiàn)在對(duì)罪犯和當(dāng)前星期幾進(jìn)行我們可以發(fā)現(xiàn)在對(duì)罪犯和當(dāng)前星期幾進(jìn)行“雙重枚舉雙重枚舉”時(shí)，時(shí)，進(jìn)行了很多重復(fù)的操作，于是我們想到，能不能不枚舉是當(dāng)進(jìn)行了很多重復(fù)的操作，于是我們想到，能不能不枚舉是當(dāng)前星期幾？這樣我們把這類(lèi)語(yǔ)句與判斷罪犯的語(yǔ)句分離，可前星期幾？這樣我們把這類(lèi)語(yǔ)句與判斷罪犯的語(yǔ)句分離，可以先由判斷罪犯的語(yǔ)句中確定一部分人肯定說(shuō)真話(huà)，一部分以先由判斷罪犯的語(yǔ)句中確定一部分人肯定說(shuō)真話(huà)，一部分人肯定說(shuō)假話(huà)，剩下的一部分人就要根據(jù)他所說(shuō)的當(dāng)前星期人肯定說(shuō)假話(huà)，剩下的一部分人就要根據(jù)他所說(shuō)的當(dāng)前星期幾的語(yǔ)句來(lái)判斷了，首先我們假設(shè)所有人判斷星期的語(yǔ)句不幾的語(yǔ)句來(lái)判斷了，首先我們假設(shè)

11、所有人判斷星期的語(yǔ)句不自相矛盾，這樣每個(gè)人將在判斷這類(lèi)問(wèn)題里面至多有一個(gè)答自相矛盾，這樣每個(gè)人將在判斷這類(lèi)問(wèn)題里面至多有一個(gè)答案，我們便可以統(tǒng)計(jì)判斷當(dāng)前是星期案，我們便可以統(tǒng)計(jì)判斷當(dāng)前是星期d d的總?cè)藬?shù)，于是改進(jìn)的總?cè)藬?shù)，于是改進(jìn)后的算法對(duì)于每一個(gè)可能的罪犯，先用后的算法對(duì)于每一個(gè)可能的罪犯，先用O(p)O(p)的時(shí)間處理所有的時(shí)間處理所有的話(huà)，再用的話(huà)，再用O(|Day|)O(|Day|)的時(shí)間枚舉星期幾。這樣，改進(jìn)后算法的時(shí)間枚舉星期幾。這樣，改進(jìn)后算法的復(fù)雜度就是的復(fù)雜度就是O(m(p+|Day|)O(m(p+|Day|)。 那么我們可不可以再進(jìn)一步，把算法優(yōu)化到線(xiàn)性？這里面可那么我們

12、可不可以再進(jìn)一步，把算法優(yōu)化到線(xiàn)性？這里面可以比較明確地告訴大家，是可以做到的，具體的算法類(lèi)似于以比較明確地告訴大家，是可以做到的，具體的算法類(lèi)似于上面的按照語(yǔ)句的種類(lèi)分離語(yǔ)句，只是分離得更細(xì)，處理得上面的按照語(yǔ)句的種類(lèi)分離語(yǔ)句，只是分離得更細(xì)，處理得更復(fù)雜，在這里就不做贅述，留給大家思考。更復(fù)雜，在這里就不做贅述，留給大家思考?，F(xiàn)有一個(gè)棱長(zhǎng)為現(xiàn)有一個(gè)棱長(zhǎng)為n的立方體，可以分成的立方體，可以分成n3個(gè)個(gè)1*1*1的單位立方體。每個(gè)單位立方體都有的單位立方體。每個(gè)單位立方體都有一個(gè)整數(shù)值。一個(gè)整數(shù)值。n3個(gè)單位立方體的數(shù)和不會(huì)超過(guò)個(gè)單位立方體的數(shù)和不會(huì)超過(guò)longint范圍。現(xiàn)在要求在這個(gè)立方體

13、找范圍。現(xiàn)在要求在這個(gè)立方體找到一個(gè)包含完整單位立方體的長(zhǎng)方體，使得該長(zhǎng)方體內(nèi)所有單位立方體的數(shù)和最大。到一個(gè)包含完整單位立方體的長(zhǎng)方體，使得該長(zhǎng)方體內(nèi)所有單位立方體的數(shù)和最大。輸入：輸入： n(1n20)；n個(gè)個(gè)n*n的數(shù)字矩陣，每個(gè)數(shù)字矩陣代表一層，每個(gè)數(shù)字代表一的數(shù)字矩陣，每個(gè)數(shù)字矩陣代表一層，每個(gè)數(shù)字代表一個(gè)單位立方體的整數(shù)值，個(gè)單位立方體的整數(shù)值，-999單位立方體的整數(shù)值單位立方體的整數(shù)值999999輸出：輸出：長(zhǎng)方體的數(shù)和長(zhǎng)方體的數(shù)和1 1、“直譯直譯”枚舉過(guò)程枚舉過(guò)程forfor x11 to n do 枚舉所有可能的平面枚舉所有可能的平面 forfor x21 to n do

14、 forfor y11 to n do forfor y21 to n do forfor z11 to n do 枚舉所有可能的上平面和下底面枚舉所有可能的上平面和下底面 forfor z21 to n do 考察狀態(tài)（考察狀態(tài)（x1，y1，z1，x2，y2，z2）；）；立方體問(wèn)題考察狀態(tài)（考察狀態(tài)（x1，y1，z1，x2，y2，z2）的任務(wù)是計(jì)算長(zhǎng)方體的體積，并調(diào)整最優(yōu)解。設(shè)）的任務(wù)是計(jì)算長(zhǎng)方體的體積，并調(diào)整最優(yōu)解。設(shè)map為立方體對(duì)應(yīng)的三維矩陣；為立方體對(duì)應(yīng)的三維矩陣；sum為當(dāng)前長(zhǎng)方體的體積；為當(dāng)前長(zhǎng)方體的體積；best為最優(yōu)解。考察過(guò)程為最優(yōu)解?？疾爝^(guò)程如下如下 sum00； for

15、for xxx1 1 to x2 do 計(jì)算長(zhǎng)方體的體積計(jì)算長(zhǎng)方體的體積 forfor yyy1 1 to y2 do forfor zzz1 1 to z2 do sumsum+mapxsum+mapx，y y，zz； 調(diào)整最優(yōu)解調(diào)整最優(yōu)解 if sumbest then bestsum if sumbest then bestsum；這個(gè)算法相當(dāng)粗糙，枚舉狀態(tài)的費(fèi)用為這個(gè)算法相當(dāng)粗糙，枚舉狀態(tài)的費(fèi)用為O O（n n9 9） 2 2、從減少重復(fù)計(jì)算入手、從減少重復(fù)計(jì)算入手記錄先前考察的結(jié)果。在統(tǒng)計(jì)長(zhǎng)方體記錄先前考察的結(jié)果。在統(tǒng)計(jì)長(zhǎng)方體2時(shí)，只要將長(zhǎng)方體時(shí)，只要將長(zhǎng)方體1的統(tǒng)計(jì)結(jié)果加上長(zhǎng)方體的

16、統(tǒng)計(jì)結(jié)果加上長(zhǎng)方體3就可以了，而就可以了，而不必按上述算法那樣重新進(jìn)行計(jì)算。不必按上述算法那樣重新進(jìn)行計(jì)算。 forfor x11 to n do 枚舉所有可能的水平面枚舉所有可能的水平面 forfor x21 to n do forfor y11 to n do forfor y21 to n do forfor z11 to n do 枚舉上平面的枚舉上平面的z軸坐標(biāo)軸坐標(biāo) begin sum00； 長(zhǎng)方體的體積初始化長(zhǎng)方體的體積初始化 forfor z21 to n do 枚舉下底面的枚舉下底面的z軸坐標(biāo)軸坐標(biāo) 考察狀態(tài)（考察狀態(tài)（x1，y1，z1，x2，y2，z2）；）； end en

17、d；forfor考察過(guò)程改為考察過(guò)程改為 forfor xxx1 1 to x2 do 計(jì)算長(zhǎng)方體的體積計(jì)算長(zhǎng)方體的體積 forfor yy y1 1 to y2 do sumsum+mapxsum+mapx，y y，z z2 2 ； if sumbest then bestsumif sumbest then bestsum； 調(diào)整最優(yōu)解調(diào)整最優(yōu)解 由于利用了計(jì)算出的結(jié)果，整個(gè)算法的時(shí)間復(fù)雜度降為由于利用了計(jì)算出的結(jié)果，整個(gè)算法的時(shí)間復(fù)雜度降為O O（n n8 8）。）。3 3、提取恰當(dāng)?shù)男畔?、提取恰?dāng)?shù)男畔⑸鲜隹疾鞂?shí)際上求出z軸坐標(biāo)為z2的平面中矩形（x1，y1，x2，y2）的數(shù)和。我們將

18、這個(gè)數(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，y2，z+ recx1，y1，z-recx2，y1，z-recx1，y2，zRecRec數(shù)組可以在輸入數(shù)據(jù)的同時(shí)計(jì)算數(shù)組可以在輸入數(shù)據(jù)的同時(shí)計(jì)算fillchar(recfillchar(rec，size(rec)size(rec)，0)0)；recrec數(shù)組初始

19、化數(shù)組初始化 forfor z1 to n do 逐層輸入信息逐層輸入信息 forfor x1 to n do 逐行輸入逐行輸入z平面的信息平面的信息 begin forfor y1 to n do 逐列輸入逐列輸入z平面上平面上x(chóng)行的信息行的信息beginbegin read(mapx read(mapx，y y，z)z)； 輸入輸入z z平面上（平面上（x,yx,y）中的數(shù)）中的數(shù) if (x=1)and(y=1) if (x=1)and(y=1) 計(jì)算計(jì)算z z平面上以（平面上以（1 1，1 1）為左上角、（）為左上角、（x,yx,y）為右下角的矩形的數(shù)和）為右下角的矩形的數(shù)和 then

20、 rec1then rec1，1 1，zmap1zmap1，1 1，zzelse if y=1 then recxelse if y=1 then recx，y y，zrecx-1zrecx-1，n n，z+mapxz+mapx，y y，zz else recx else recx，y y，zrecxzrecx，y-1y-1，z+mapxz+mapx，y y，zz； end end；forfor readln readln； end end；forfor這樣，考察過(guò)程就可以改為這樣，考察過(guò)程就可以改為 sumsum+recxsumsum+recx2 2，y y2 2，z z2 2+recx+r

21、ecx1 1，y y1 1，z z2 2-recx-recx2 2，y y1 1，z z2 2-recx-recx1 1，y y2 2，z z2 2 ； if sumbest then bestsum if sumbest then bestsum；時(shí)間復(fù)雜度降為時(shí)間復(fù)雜度降為O O（n n6 6）。）。如果長(zhǎng)方體如果長(zhǎng)方體a的數(shù)和是負(fù)數(shù)，則長(zhǎng)方體的數(shù)和是負(fù)數(shù)，則長(zhǎng)方體a的計(jì)算結(jié)的計(jì)算結(jié)果廢棄，考察長(zhǎng)方體果廢棄，考察長(zhǎng)方體b-a。因?yàn)殚L(zhǎng)方體。因?yàn)殚L(zhǎng)方體b的數(shù)和的數(shù)和=長(zhǎng)方體長(zhǎng)方體b-a的數(shù)和的數(shù)和+長(zhǎng)方體長(zhǎng)方體a的數(shù)和，由于長(zhǎng)方體的數(shù)和，由于長(zhǎng)方體a的數(shù)和為負(fù)，長(zhǎng)方體的數(shù)和為負(fù)，長(zhǎng)方體b-a的

22、數(shù)和一定大于等于長(zhǎng)的數(shù)和一定大于等于長(zhǎng)方體方體b的數(shù)和。由此可見(jiàn)，在累計(jì)長(zhǎng)方體數(shù)和的的數(shù)和。由此可見(jiàn)，在累計(jì)長(zhǎng)方體數(shù)和的時(shí)候，只要由上而下地枚舉長(zhǎng)方體下底面的時(shí)候，只要由上而下地枚舉長(zhǎng)方體下底面的z軸軸坐標(biāo)即可。設(shè)坐標(biāo)即可。設(shè)total(z)以以z軸坐標(biāo)為軸坐標(biāo)為z的平面為下底面的長(zhǎng)方的平面為下底面的長(zhǎng)方體的最大數(shù)和體的最大數(shù)和0, 1, 1, 1, 1,)1(, 0max(00)(21121122zzyxreczyxreczyxreczyxrecztotalzZTOTALforfor x11 to n do 枚舉所有可能的子平面枚舉所有可能的子平面 forfor x21 to n do fo

23、rfor y11 to n do forfor y21 to n do begin total00； 長(zhǎng)方體以長(zhǎng)方體以(x(x1 1,y,y1 1) )為左上角為左上角,(x,(x2 2,y,y2 2) )為右下角）的最大數(shù)和初始化為右下角）的最大數(shù)和初始化 for for z1 to n do 枚舉枚舉長(zhǎng)方體長(zhǎng)方體b b下底面的下底面的z z軸坐標(biāo)軸坐標(biāo) begin totalmaxtotaltotalmaxtotal，0+0+ recx2，y2，z+ recx1-1，y1-1，z-recx2，y1-1，z-recx-1-1，y2，z； 計(jì)算以計(jì)算以z為下底面的長(zhǎng)方體為下底面的長(zhǎng)方體b的最大

24、數(shù)和的最大數(shù)和 if total best then besttotaltotal； 調(diào)整最優(yōu)解調(diào)整最優(yōu)解 end end；forfor end end；forfor這一改進(jìn)使得考察的狀態(tài)整數(shù)降為這一改進(jìn)使得考察的狀態(tài)整數(shù)降為O(nO(n5 5) ) 子串子串 給定一個(gè)由自然數(shù)串聯(lián)而成的無(wú)限數(shù)列1234567891011121314（母串） 求任意一個(gè)長(zhǎng)度不超過(guò)200的數(shù)列（子串）在其中最早出現(xiàn)的位置。分析： 首先，由于母串可無(wú)限擴(kuò)充，顯然我們不可能把它全部生成出來(lái)。 如果邊生成母串，邊判斷所生成的數(shù)串是否包含給定的子串，即使是使用字符串處理中高效的KMP算法，耗費(fèi)的工作量也是巨大的。1121

25、314 先枚舉第1位1 自然數(shù)1之后為2,3, 母串中形如123 與子串從第2位開(kāi)始不符 枚舉前2位11 自然數(shù)11之后為12,13 母串中形如111213 與子串從第3位開(kāi)始不符 考慮第2位開(kāi)始12 自然數(shù)12之前為11,末位與子串第1位相同，之后為13,14, 母串中形如1314 與子串匹配！如何優(yōu)化呢？ 較好的方法是另辟蹊徑： 剛才我們枚舉的是母串的每一位，不妨換一個(gè)角度，從子串著手。 先來(lái)觀(guān)察一些片斷： 12345678910111213141516很自然得到算法：枚舉子串所包含第一個(gè)完整的數(shù)a的位數(shù)La。假設(shè)a在母串的第k位出現(xiàn)（k=La）判斷接下來(lái)由a生成的序列是否與子串吻合。如果

26、吻合，則最優(yōu)解的判斷：(1) LaAns_k4跟據(jù)Ans_a及Ans_k計(jì)算出位數(shù) 總時(shí)間復(fù)雜度約為O(n3)，與之前的不可估量相比有了本質(zhì)性提高。 第4步可通過(guò)多種途徑求得，這里不作介紹。 由于其中牽涉到許多高精度的計(jì)算及字符串處理，要求我們細(xì)致認(rèn)真。小結(jié) 充分挖掘題目特性是解決本題的關(guān)鍵。 得以使枚舉這類(lèi)看似低效率的方法得到較好的運(yùn)用。 同時(shí)細(xì)致全面的考慮問(wèn)題也是必不可少的。寬度優(yōu)先遍歷算法框架 從某個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)從某個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)v出發(fā)出發(fā),依次訪(fǎng)問(wèn)依次訪(fǎng)問(wèn)v的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)的鄰接點(diǎn).然后分別從這些鄰接點(diǎn)出發(fā)廣度優(yōu)先搜索遍歷然后分別從這些鄰接點(diǎn)出發(fā)廣度優(yōu)先搜索

27、遍歷,直直到所有已被訪(fǎng)問(wèn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)到到所有已被訪(fǎng)問(wèn)的鄰接點(diǎn)都被訪(fǎng)問(wè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 not visitedw then visite(w);visitedw:=true; enqueue(q,w) w:=NEXTADJ(v,w); ENDP神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)(NOIP2003-1) 在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)在蘭蘭的模型中，

28、神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱(chēng)為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下稱(chēng)為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下圖是一個(gè)神經(jīng)元的例子：圖是一個(gè)神經(jīng)元的例子： 圖中，圖中，X1X1X3X3是信息輸入渠道，是信息輸入渠道，Y1Y1Y2Y2是信息輸出渠道，是信息輸出渠道，C1C1表示神經(jīng)元目前的狀態(tài)，表示神經(jīng)元目前的狀態(tài)，UiUi是閾值，可視為神經(jīng)元的一個(gè)是閾值，可視為神經(jīng)元的一個(gè)內(nèi)在參數(shù)。內(nèi)在參數(shù)。 神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱(chēng)為輸入層、的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)

29、分為幾層；稱(chēng)為輸入層、輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。輸出信息，只從上一層神經(jīng)元接受信息。 神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)蘭蘭規(guī)定，蘭蘭規(guī)定，C Ci i服從公式：（其中服從公式：（其中n n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）E) i , j (ijjiiUCWC 公式中的公式中的WjiWji（可能為負(fù)值）表示連接（可能為負(fù)值）表示連接j j號(hào)神經(jīng)元和號(hào)神經(jīng)元和 i i號(hào)神經(jīng)號(hào)神經(jīng)元的邊的權(quán)值。當(dāng)元的邊的權(quán)值。當(dāng) CiCi大于大于0 0時(shí)，該神經(jīng)元處于興奮狀態(tài)，否時(shí)，該神經(jīng)元處于興奮

30、狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)向其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為向其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為CiCi。 如此在輸入層如此在輸入層神經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)神經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)行運(yùn)作。現(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的行運(yùn)作?，F(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（狀態(tài)（CiCi），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。 【輸入格式【輸入格式】 第一行是兩個(gè)整數(shù)第一行是兩個(gè)整數(shù)n n（1

31、n201n20）和）和p p。接下來(lái)。接下來(lái)n n行，每行兩個(gè)行，每行兩個(gè)整數(shù)，第整數(shù)，第i i1 1行是神經(jīng)元行是神經(jīng)元i i最初狀態(tài)和其閾值（最初狀態(tài)和其閾值（UiUi），非輸入），非輸入層的神經(jīng)元開(kāi)始時(shí)狀態(tài)必然為層的神經(jīng)元開(kāi)始時(shí)狀態(tài)必然為0 0。再下面。再下面P P行，每行由兩個(gè)整行，每行由兩個(gè)整數(shù)數(shù)i i，j j及一個(gè)整數(shù)及一個(gè)整數(shù)WijWij，表示連接神經(jīng)元，表示連接神經(jīng)元i i、j j的邊權(quán)值為的邊權(quán)值為WijWij。【輸出格式【輸出格式】 輸出包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的輸出包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的編號(hào)，及其最后的狀態(tài)，兩個(gè)整數(shù)間以空格

32、分隔。編號(hào)，及其最后的狀態(tài)，兩個(gè)整數(shù)間以空格分隔。僅輸出最僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順序輸出！序輸出！ 若輸出層的神經(jīng)元最后狀態(tài)均為若輸出層的神經(jīng)元最后狀態(tài)均為 0 0，則輸出，則輸出 NULLNULL。分析 理解問(wèn)題的第一步就是認(rèn)真理解問(wèn)題的第一步就是認(rèn)真“讀題讀題”。那么我們先來(lái)看。那么我們先來(lái)看一看這個(gè)題目涉及的問(wèn)題。研究一下題目中所給的圖的一看這個(gè)題目涉及的問(wèn)題。研究一下題目中所給的圖的一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：一些性質(zhì)，可以發(fā)現(xiàn)如下特點(diǎn)：1 1圖中所有的節(jié)點(diǎn)都有一個(gè)確定的等級(jí)，我們記作圖中所有的節(jié)點(diǎn)

33、都有一個(gè)確定的等級(jí)，我們記作Level(i)Level(i)2 2圖中所有的邊都是有向的，并且從圖中所有的邊都是有向的，并且從LevelLevel值為值為i-1i-1的節(jié)的節(jié)點(diǎn)指向點(diǎn)指向LevelLevel值為值為i i的節(jié)點(diǎn)的節(jié)點(diǎn) 我們不妨將其抽象為我們不妨將其抽象為“階段圖階段圖”。 更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無(wú)環(huán)的，更一般地，我們可以發(fā)現(xiàn)所有的階段圖都是有向無(wú)環(huán)的，這樣我們可以通過(guò)拓?fù)渑判騺?lái)得到期望的處理節(jié)點(diǎn)的順這樣我們可以通過(guò)拓?fù)渑判騺?lái)得到期望的處理節(jié)點(diǎn)的順序。序。可行算法 由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級(jí)由于階段圖的性質(zhì)使得該圖的所有邊所連接節(jié)點(diǎn)的等級(jí)

34、都是相鄰的，因此就可以設(shè)計(jì)出一個(gè)基于寬度優(yōu)先搜索都是相鄰的，因此就可以設(shè)計(jì)出一個(gè)基于寬度優(yōu)先搜索（即（即BFSBFS）的算法：）的算法：1 1初始時(shí)將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；初始時(shí)將所有輸入層的節(jié)點(diǎn)放入隊(duì)列；2 2取出隊(duì)列中的一個(gè)元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的取出隊(duì)列中的一個(gè)元素，不重復(fù)地?cái)U(kuò)展并處理該節(jié)點(diǎn)所發(fā)出的邊的目標(biāo)節(jié)點(diǎn)；邊的目標(biāo)節(jié)點(diǎn)；3 3如果隊(duì)列非空，則轉(zhuǎn)向如果隊(duì)列非空，則轉(zhuǎn)向2 2；4 4輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。 但是由于本題在問(wèn)題描述中并沒(méi)有明確的給出判斷一個(gè)但是由于本題在問(wèn)題描述中并沒(méi)有明確的給出判斷一個(gè)節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需

35、要在算法進(jìn)行的過(guò)程當(dāng)中節(jié)點(diǎn)是否是輸入節(jié)點(diǎn)，因此需要在算法進(jìn)行的過(guò)程當(dāng)中額外地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過(guò)程即便是真實(shí)額外地考慮一些邊界情況的數(shù)據(jù)（這個(gè)過(guò)程即便是真實(shí)數(shù)據(jù)沒(méi)有這樣出也是要有的），下面給出的更一般的算數(shù)據(jù)沒(méi)有這樣出也是要有的），下面給出的更一般的算法可能會(huì)更好的跳過(guò)這些邊界情況。法可能會(huì)更好的跳過(guò)這些邊界情況。1 1對(duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍粚?duì)原圖中所有的節(jié)點(diǎn)進(jìn)行一次拓?fù)渑判颍? 2按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；按照拓?fù)漤樞蛱幚砻恳粋€(gè)節(jié)點(diǎn)；3 3輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。輸出輸出層中所有滿(mǎn)足條件的節(jié)點(diǎn)。Amazing Robots: IOI2003已知條件： 迷宮

36、i（i=1,2） （每個(gè)不會(huì)大于20*20） 守衛(wèi) Gi（0=Gi=10） （守衛(wèi)循環(huán)移動(dòng)進(jìn)行執(zhí)勤） （守衛(wèi)巡邏的方格數(shù)（2.4）求： 兩個(gè)機(jī)器人都離開(kāi)迷宮所用的最少指令數(shù)目 和離開(kāi)制指令序列（10000 步以?xún)?nèi)）。每一步可以發(fā)出的命令可以是N, E, S, W中的一種，有4種選擇。對(duì)每一步具體發(fā)出哪個(gè)命令，直接搜索。假設(shè)最后結(jié)果是T。（也就是最少出宮時(shí)間）時(shí)間復(fù)雜度是O(4T)這種方法時(shí)間復(fù)雜度太高，絕對(duì)不可行!5*4和4*4的迷宮第一個(gè)機(jī)器人的位置是(2,2)第二個(gè)機(jī)器人的位置是(3,2)當(dāng)前時(shí)間是0。狀態(tài)(2,2),(3,2),0)狀態(tài)表示：狀態(tài)表示： （第一個(gè)機(jī)器人位置，第二個(gè)機(jī)器認(rèn)位

37、置，時(shí)間）（第一個(gè)機(jī)器人位置，第二個(gè)機(jī)器認(rèn)位置，時(shí)間）E(2,2),(3,2),0)(2,3),(3,3),1)時(shí)間已知，則所有Guard的位置可知。Guard、Robot的位置均已知，所以狀態(tài)可以轉(zhuǎn)移0時(shí)刻1時(shí)刻2時(shí)刻3時(shí)刻0時(shí)刻和2時(shí)刻是一樣的1時(shí)刻和3時(shí)刻是一樣的。稍加分析：此Guard循環(huán)以2為周期循環(huán)。狀態(tài)轉(zhuǎn)移，需要的信息是：Robot位置，Guard位置。Position of Robot1, 2是的作用就是記錄Robot位置。Time的作用就是為了計(jì)算Guard的位置狀態(tài)：(position of Robot1, position of Robot2, Time)Time=100

38、00，這是狀態(tài)數(shù)過(guò)多的罪魁禍?zhǔn)?！題目說(shuō)：Guard巡邏經(jīng)過(guò)的格子數(shù)只可能是2, 3, 4。也就是說(shuō)機(jī)器人巡邏周期只能是2, 4, 6。2, 4, 6=12，所以第0時(shí)刻、12時(shí)刻、24時(shí)刻Guard的狀態(tài)完全相同。12可以看作Guard的周期。Time只要記錄當(dāng)前是第幾個(gè)周期。因?yàn)橹芷诖_定了，Guard的位置也完全確定了！ 0=Time=11狀態(tài)數(shù)狀態(tài)數(shù)(n*n)*(n*n)*12=12n4。用用BFS算法，標(biāo)志數(shù)組判重。算法，標(biāo)志數(shù)組判重。時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(12n4)。n=20完全可以承受完全可以承受 -深度優(yōu)先遍歷 從某個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)從某個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)v出發(fā)出發(fā),深度優(yōu)先遍歷圖深

39、度優(yōu)先遍歷圖,直到直到和和v有路徑的頂點(diǎn)都訪(fǎng)問(wèn)到有路徑的頂點(diǎn)都訪(fǎng)問(wè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討論討論:蟲(chóng)食算問(wèn)題蟲(chóng)食算問(wèn)題 給出一個(gè)給出一個(gè)N進(jìn)制的蟲(chóng)食算式，相同的字母代表相進(jìn)制的蟲(chóng)食算式，相同的字母代表相同的數(shù)字，不同的字母代表不同的數(shù)字。要求求同的數(shù)字，不同的字母代表不同的數(shù)字。要求求出滿(mǎn)足這個(gè)算式的唯一一組解，也就是字母和數(shù)出滿(mǎn)足這個(gè)算式的唯一一組解，也就是字母和數(shù)字的一一對(duì)應(yīng)關(guān)系

40、字的一一對(duì)應(yīng)關(guān)系.解決方案解決方案1:要求一一對(duì)應(yīng)的關(guān)系，就可以枚舉這些一要求一一對(duì)應(yīng)的關(guān)系，就可以枚舉這些一一對(duì)應(yīng)的關(guān)系，找出符合的一項(xiàng)。這樣，一對(duì)應(yīng)的關(guān)系，找出符合的一項(xiàng)。這樣，關(guān)系總數(shù)有關(guān)系總數(shù)有O(N!)個(gè)，最壞情況下必須枚舉個(gè)，最壞情況下必須枚舉所有的關(guān)系，并且加以判斷，復(fù)雜度高達(dá)所有的關(guān)系，并且加以判斷，復(fù)雜度高達(dá)O(N*N!)！ 解決方案解決方案2: 大體上，從算式最后一位開(kāi)始模擬運(yùn)算情況，當(dāng)可遞推時(shí)遞推，大體上，從算式最后一位開(kāi)始模擬運(yùn)算情況，當(dāng)可遞推時(shí)遞推，不可遞推則枚舉。不可遞推則枚舉。 對(duì)于一豎列，先處理兩個(gè)加數(shù)，當(dāng)遇到的字母的值不確定時(shí)，對(duì)于一豎列，先處理兩個(gè)加數(shù)，當(dāng)遇

41、到的字母的值不確定時(shí)，則枚舉當(dāng)前位（注意與前面的情況判重）；否則不作為處理和，則枚舉當(dāng)前位（注意與前面的情況判重）；否則不作為處理和，當(dāng)遇到的字母的值不確定時(shí)當(dāng)遇到的字母的值不確定時(shí),可從加數(shù)部分確定的值來(lái)確定可從加數(shù)部分確定的值來(lái)確定（注意與前面的情況判重和進(jìn)位）；否則看加數(shù)部分確定的值（注意與前面的情況判重和進(jìn)位）；否則看加數(shù)部分確定的值是否能得到和部分（注意進(jìn)位）。引出矛盾就回溯。是否能得到和部分（注意進(jìn)位）。引出矛盾就回溯。 如題目的樣例：如題目的樣例： 5 ABCED BDACE EBBAA 它最后一位的情況是它最后一位的情況是(D+E) mod N=A, 對(duì)于最后一位只要枚舉對(duì)于最

42、后一位只要枚舉D,E的情況；的情況；A 則可以由則可以由D,E的值遞推而來(lái)。對(duì)于倒的值遞推而來(lái)。對(duì)于倒2位位, (E+C+最后一位進(jìn)位最后一位進(jìn)位) mod N=A ；E的值可以用前面的結(jié)果；的值可以用前面的結(jié)果；枚舉枚舉C；判斷；判斷A是否為是否為(D+C+最后一位進(jìn)位最后一位進(jìn)位) mod N雖然復(fù)雜度還是雖然復(fù)雜度還是O(N!)，但這種方法限制很多（相當(dāng)于剪，但這種方法限制很多（相當(dāng)于剪枝）。枝）。 解決方案解決方案3: 觀(guān)察題目的條件已經(jīng)限制得很苛刻：觀(guān)察題目的條件已經(jīng)限制得很苛刻：N個(gè)變量，每個(gè)個(gè)變量，每個(gè)至少出現(xiàn)一次；而且正好一共有至少出現(xiàn)一次；而且正好一共有N位的算式。這樣就位的

43、算式。這樣就構(gòu)成了解方程的動(dòng)機(jī)。這構(gòu)成了解方程的動(dòng)機(jī)。這N個(gè)變量的對(duì)應(yīng)個(gè)變量的對(duì)應(yīng)N個(gè)未知量，個(gè)未知量，有有N位的算式對(duì)應(yīng)位的算式對(duì)應(yīng)N個(gè)方程；個(gè)方程；N個(gè)未知量，個(gè)未知量，N個(gè)方程，個(gè)方程，正好可以得到唯一解。這里要注意，對(duì)解的要求很?chē)?yán)正好可以得到唯一解。這里要注意，對(duì)解的要求很?chē)?yán)格：必須是格：必須是0至至N-1的每個(gè)整數(shù)都正好出現(xiàn)一次。的每個(gè)整數(shù)都正好出現(xiàn)一次。但對(duì)每位式子的進(jìn)位關(guān)系并不清楚，而進(jìn)位關(guān)系但對(duì)每位式子的進(jìn)位關(guān)系并不清楚，而進(jìn)位關(guān)系正好影響了方程的常數(shù)項(xiàng)。枚舉每位是否進(jìn)位。用時(shí)正好影響了方程的常數(shù)項(xiàng)。枚舉每位是否進(jìn)位。用時(shí)O(2n), (因?yàn)槭孜徊豢赡苓M(jìn)位，無(wú)須枚舉因?yàn)槭孜徊豢?/p>

44、能進(jìn)位，無(wú)須枚舉)。然后，用。然后，用高斯消元法來(lái)解方程?？梢栽诿杜e之前先解出方程，高斯消元法來(lái)解方程。可以在枚舉之前先解出方程，枚舉的時(shí)候再把參數(shù)帶入。帶入求解的復(fù)雜度是枚舉的時(shí)候再把參數(shù)帶入。帶入求解的復(fù)雜度是O(n2) 。 解決方案解決方案4: 在解決方案在解決方案3的基礎(chǔ)上，我們可以對(duì)進(jìn)位的枚舉剪枝。的基礎(chǔ)上，我們可以對(duì)進(jìn)位的枚舉剪枝。觀(guān)察這個(gè)豎列：觀(guān)察這個(gè)豎列：A+B=C，若無(wú)進(jìn)位則有，若無(wú)進(jìn)位則有A=C且且BC且且B=C.若能推導(dǎo)出若能推導(dǎo)出A=A （A,B為任何不相等為任何不相等字母），則當(dāng)前的枚舉不可行?？捎眠f歸枚舉，從字母），則當(dāng)前的枚舉不可行?？捎眠f歸枚舉，從后向前枚舉，處

45、理一個(gè)豎列時(shí)則加上后向前枚舉，處理一個(gè)豎列時(shí)則加上2個(gè)不等式，看個(gè)不等式，看是否矛盾。數(shù)據(jù)結(jié)構(gòu)用鄰接矩陣。（規(guī)定是否矛盾。數(shù)據(jù)結(jié)構(gòu)用鄰接矩陣。（規(guī)定A=B，再，再有向圖中有邊有向圖中有邊）。）。 若加進(jìn)不等式若加進(jìn)不等式A=B ，要加入所有，要加入所有x(x=A) =y(B=y)，枚舉，枚舉x,y用用O(n2)得時(shí)間。再判斷是否得時(shí)間。再判斷是否有有x=y.森林中的果樹(shù) 森林中長(zhǎng)著一種奇怪的果樹(shù),在每個(gè)分叉處生長(zhǎng)著果實(shí)，小蟲(chóng)Nileh和Nixed的食物就是這些果實(shí)！他們準(zhǔn)備把果樹(shù)分成兩部分，每個(gè)蟲(chóng)蟲(chóng)得到各自的一部分，而分果樹(shù)的方法就是選擇一個(gè)分叉點(diǎn)，蟲(chóng)蟲(chóng)將他們咬斷（自然分叉點(diǎn)上的果實(shí)也被扔掉了

46、），這樣果樹(shù)就變成了兩個(gè)部分：分叉點(diǎn)上面的部分和分叉點(diǎn)下面的部分。 （注意,每個(gè)部分不一定是連在一起的）,比如對(duì)于右邊這顆果樹(shù)，如果他們咬掉藍(lán)色的果子，那么就被分為紅色和黃色的兩個(gè)部分。 被咬掉的果子會(huì)被浪費(fèi)，他們想盡可能的減少浪費(fèi)，于是蟲(chóng)蟲(chóng)給每個(gè)果子一個(gè)美味值，對(duì)于每個(gè)果子，請(qǐng)計(jì)算如果咬掉這個(gè)果子，它上面部分、下面部分和從樹(shù)根到這個(gè)分叉點(diǎn)的路徑中比這個(gè)果子更美味的果子各有多少個(gè)。 分析圖例算法 考慮一個(gè)點(diǎn)P，對(duì)樹(shù)進(jìn)行從左到右的深度優(yōu)先遍歷，那么在A(yíng),D部分的點(diǎn)會(huì)在P之前被訪(fǎng)問(wèn)，B,C在之后被訪(fǎng)問(wèn)。 同理，從右到左深度優(yōu)先遍歷，那么B,D先被訪(fǎng)問(wèn)，A,C后被訪(fǎng)問(wèn)。 對(duì)于求出的這兩個(gè)序列，可以用

47、nlogn求出序列中每個(gè)點(diǎn)之前有多少個(gè)點(diǎn)比它大。 也就是我們可以求出每個(gè)點(diǎn)的Fa+Fd，F(xiàn)b+Fd（Fi表示在i部分中有多少點(diǎn)比固定點(diǎn)大） Fd可以用一遍深度優(yōu)先遍歷求出。最長(zhǎng)上升序列 設(shè)有整數(shù)序列設(shè)有整數(shù)序列b b1 1,b,b2 2,b,b3 3, ,b,bm m ，若存在下標(biāo)，若存在下標(biāo)i1i2i3i1i2i3inin，且且b bi1i1bbi2i2bbi3i3 bbinin，則，則稱(chēng)稱(chēng) b b1 1,b,b2 2,b,b3 3, ,b,bm m中有長(zhǎng)度為中有長(zhǎng)度為n n的上升序列的上升序列b bi1 i1 , , b bi2 i2 ,b,bi3 i3 , ,b,binin 。 求序列求

48、序列b b1 1,b,b2 2,b,b3 3, ,b,bm m的最大上升長(zhǎng)度的最大上升長(zhǎng)度n,n,以以及所有長(zhǎng)度為及所有長(zhǎng)度為n n的的最大上升子序列個(gè)數(shù)最大上升子序列個(gè)數(shù)t t 輸入：整數(shù)序列。輸入：整數(shù)序列。 輸出：輸出：n,tn,t分析（1 1）設(shè)）設(shè)f f(i)為前為前i個(gè)數(shù)中的最大不下降序列長(zhǎng)度個(gè)數(shù)中的最大不下降序列長(zhǎng)度 , 則則 f(i)=maxf(j)+1 (1=jif(i)=maxf(j)+1 (1=ji=m=m, bj, bjbi)bi) 邊界為邊界為F(1)=1F(1)=1(2)設(shè)設(shè)t t(i)(i)為前為前i i個(gè)數(shù)中最長(zhǎng)不下降序列的個(gè)數(shù)個(gè)數(shù)中最長(zhǎng)不下降序列的個(gè)數(shù), ,則

49、則 t(i)=t(j) (t(i)=t(j) (1=ji1=ji=m , bj=m , bjbi, f(i)=f(j)-1) bi, f(i)=f(j)-1) 初始為初始為t t(i)=1(i)=1 當(dāng)當(dāng)f(i)=nf(i)=n時(shí)，將時(shí)，將t(i)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時(shí)，時(shí)，邊界為邊界為tt=4=4進(jìn)一步(3)求本質(zhì)不同的最長(zhǎng)不下降序列個(gè)數(shù)有多少個(gè)？求本質(zhì)不同的最長(zhǎng)不下降序列個(gè)數(shù)有多少個(gè)？ 如：如：1 2 3 4 6 5 8 10 9 有，有，

50、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ì)不同的。都是本質(zhì)不同的。 但對(duì)于但對(duì)于 1 2 2 3 3 5 4 f 1 2 2 3 3 5 4 t 1 1 1 2 2 4 4 答案有答案有8個(gè)，其中個(gè)，其中4個(gè)個(gè)1 2 3 5 ，4個(gè)個(gè)1 2 3 4改進(jìn)算法 上例顯然對(duì)于相兩個(gè)相同的數(shù)，重復(fù)算了多次因上例顯然對(duì)于相兩個(gè)相同的數(shù)，重復(fù)算了多次因此，我們對(duì)算法進(jìn)行改進(jìn)：此，我們對(duì)算法進(jìn)行改進(jìn)： 對(duì)原序列按對(duì)原序列按b b從小到大（當(dāng)從小到大（當(dāng)bi=bjbi=bj時(shí)按時(shí)按F F從大到?。拇蟮叫。┡判?，增設(shè)排序

51、，增設(shè)Order(i)Order(i)記錄新序列中的記錄新序列中的i i個(gè)數(shù)在原個(gè)數(shù)在原序列中的位置?？梢?jiàn)，序列中的位置?？梢?jiàn)， 求求t(i)t(i)時(shí)，當(dāng)時(shí)，當(dāng)f f(j)=f(j+1),b(j)=b(j+1)(j)=f(j+1),b(j)=b(j+1)且且Order(j+1)Order(i)Order(j+1)Order(i)時(shí)，便不累加時(shí)，便不累加t(j)t(j)。這樣。這樣就避免了重復(fù)。就避免了重復(fù)。 上述算法的時(shí)間復(fù)雜度為上述算法的時(shí)間復(fù)雜度為O(n2) 合唱隊(duì)形合唱隊(duì)形(NOIP2005-3) 給出給出N個(gè)人，第個(gè)人，第i個(gè)人的高度為個(gè)人的高度為Ai,現(xiàn)在要求現(xiàn)在要求找出一個(gè)對(duì)形找

52、出一個(gè)對(duì)形,使得從某個(gè)人開(kāi)始使得從某個(gè)人開(kāi)始,前面的人前面的人都呈遞增的順序排列都呈遞增的順序排列,后面的人呈遞減順序后面的人呈遞減順序排列排列 找出最長(zhǎng)的該隊(duì)列找出最長(zhǎng)的該隊(duì)列.解法解法 動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃： 枚舉中間最高的一個(gè)人，接著對(duì)它的左邊求最長(zhǎng)上升序枚舉中間最高的一個(gè)人，接著對(duì)它的左邊求最長(zhǎng)上升序列（注意序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)），對(duì)右邊求列（注意序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)），對(duì)右邊求最長(zhǎng)下降序列（同樣的，序列中最高的同學(xué)不應(yīng)高過(guò)基最長(zhǎng)下降序列（同樣的，序列中最高的同學(xué)不應(yīng)高過(guò)基準(zhǔn)）。時(shí)間復(fù)雜度為準(zhǔn)）。時(shí)間復(fù)雜度為O(n2)，算法實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單。，算法實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單。 接著

53、對(duì)這個(gè)算法進(jìn)行分析，我們不難發(fā)現(xiàn)，假如還是基接著對(duì)這個(gè)算法進(jìn)行分析，我們不難發(fā)現(xiàn)，假如還是基于枚舉一個(gè)同學(xué)的話(huà)，設(shè)于枚舉一個(gè)同學(xué)的話(huà)，設(shè)Incsqi表示了表示了1 - i的最長(zhǎng)上升的最長(zhǎng)上升序列，序列，Decsqi表示了表示了i - n的最長(zhǎng)下降序列，那么，的最長(zhǎng)下降序列，那么， Currenti = Incsqi + Decsqi - 1（兩個(gè)數(shù)組中（兩個(gè)數(shù)組中i被重被重復(fù)計(jì)算了）復(fù)計(jì)算了） 那么，我們只需要先求好最長(zhǎng)上升和下降序列，然后枚那么，我們只需要先求好最長(zhǎng)上升和下降序列，然后枚舉中間最高的同學(xué)就可以了。舉中間最高的同學(xué)就可以了。優(yōu)化優(yōu)化 求最長(zhǎng)上升序列的經(jīng)典狀態(tài)轉(zhuǎn)移方程為：求最長(zhǎng)上

54、升序列的經(jīng)典狀態(tài)轉(zhuǎn)移方程為： opti = maxoptj+1, 其中其中ijlisti 我們對(duì)狀態(tài)轉(zhuǎn)移方程稍微做一些修改：我們對(duì)狀態(tài)轉(zhuǎn)移方程稍微做一些修改： opti = maxopt(i+1), minj | recj=listi recj 記錄當(dāng)前不下降序列的最小值記錄當(dāng)前不下降序列的最小值 很明顯可以看出，在很明顯可以看出，在opti的尋找的尋找j的過(guò)程當(dāng)中，的過(guò)程當(dāng)中，查詢(xún)序列是單調(diào)的，于是可以用二分法，就十分查詢(xún)序列是單調(diào)的，于是可以用二分法，就十分巧妙地在巧妙地在logn的時(shí)間內(nèi)找到指定的的時(shí)間內(nèi)找到指定的j，而問(wèn)題的，而問(wèn)題的總體復(fù)雜度為總體復(fù)雜度為O(nlogn)。這樣，這個(gè)

55、問(wèn)題的算法。這樣，這個(gè)問(wèn)題的算法效率就得到了大幅度的提升，即便效率就得到了大幅度的提升，即便n是是106，也可，也可以輕松應(yīng)對(duì)。以輕松應(yīng)對(duì)。二叉堆 定義定義 n個(gè)元素的序列個(gè)元素的序列k1,k2,kn，當(dāng)且僅當(dāng)滿(mǎn)，當(dāng)且僅當(dāng)滿(mǎn)足足 ki=k2i 并且并且 ki =k2i 并且并且 ki = k2i+1 二叉堆肯定是一顆完全二叉樹(shù)二叉堆肯定是一顆完全二叉樹(shù)堆的構(gòu)造 第一步第一步,構(gòu)構(gòu)造一個(gè)初始造一個(gè)初始堆堆 第二步第二步,逐逐步調(diào)整該堆步調(diào)整該堆,使它符合堆使它符合堆的性質(zhì)的性質(zhì)堆排序算法PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I;

56、x:=rk.key;finish:=false t:=rk; while (j=m) and not finish do if (jrj+1.key) 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合并果子合并果子 把合成堆后的每堆的果子仍然看成相對(duì)獨(dú)立的，把

57、合成堆后的每堆的果子仍然看成相對(duì)獨(dú)立的，那么定義那么定義timesi等于第等于第i堆果子被合并的次數(shù)，堆果子被合并的次數(shù)，ai為第為第i堆數(shù)字權(quán)值。則堆數(shù)字權(quán)值。則 Totalcost= ，目，目標(biāo)求得是標(biāo)求得是 minTotalcost。 建立一棵二叉樹(shù)，每堆果子分別為該樹(shù)的葉節(jié)點(diǎn)，建立一棵二叉樹(shù)，每堆果子分別為該樹(shù)的葉節(jié)點(diǎn)，一種二叉樹(shù)形態(tài)對(duì)應(yīng)一種合并方案（一種二叉樹(shù)形態(tài)對(duì)應(yīng)一種合并方案（2堆果子合堆果子合并則有共同父結(jié)點(diǎn)），所以該方案的并則有共同父結(jié)點(diǎn)），所以該方案的Totalcost =depthi*vi ，i是葉節(jié)點(diǎn)。解法是每次取出最小的是葉節(jié)點(diǎn)。解法是每次取出最小的兩個(gè)節(jié)點(diǎn)，并從節(jié)點(diǎn)

58、集合中刪除，然后合并這兩兩個(gè)節(jié)點(diǎn)，并從節(jié)點(diǎn)集合中刪除，然后合并這兩點(diǎn)后再加入節(jié)點(diǎn)集合；重復(fù)，直到只剩一個(gè)節(jié)點(diǎn)；點(diǎn)后再加入節(jié)點(diǎn)集合；重復(fù)，直到只剩一個(gè)節(jié)點(diǎn)； niiivtimes1 由于每次要取出最小的兩個(gè)節(jié)點(diǎn)。一般做法是每更由于每次要取出最小的兩個(gè)節(jié)點(diǎn)。一般做法是每更新一次集合，重新排序，時(shí)間是新一次集合，重新排序，時(shí)間是O(n2)。由于。由于n=10000，不得不采用數(shù)據(jù)結(jié)構(gòu)，不得不采用數(shù)據(jù)結(jié)構(gòu)-堆進(jìn)行優(yōu)化。堆進(jìn)行優(yōu)化。 )(2n)log(nn解決方案解決方案方法或要點(diǎn)方法或要點(diǎn) 時(shí)間復(fù)雜時(shí)間復(fù)雜度度可過(guò)數(shù)據(jù)可過(guò)數(shù)據(jù)解決方案解決方案1 一般做法一般做法30%-50%解決方案解決方案2堆堆10

59、0%最大子序和最大子序和問(wèn)題描述 輸入一個(gè)長(zhǎng)度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的長(zhǎng)度不超過(guò)M的子序列，使得這個(gè)序列的和最大。最大子序和例如： 序列 1， -3， 5， 1， -2， 3當(dāng)M=2或3時(shí)S=5+1=6當(dāng)M=4時(shí)S=5+1+(-2)+3=7數(shù)據(jù)范圍: 50%的數(shù)據(jù)N,M=1000 100%的數(shù)據(jù)N,M=20000一個(gè)簡(jiǎn)化的問(wèn)題序列的最大連續(xù)和 輸入一個(gè)長(zhǎng)度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的子序列，使得這個(gè)序列的和最大。 和原問(wèn)題相比沒(méi)有M這個(gè)序列長(zhǎng)度的限制！分析：分析： 設(shè) F(i)表示以第i個(gè)數(shù)結(jié)尾的最大連續(xù)和 以第i個(gè)數(shù)結(jié)尾的最大連續(xù)和序列，可

60、能存在兩種選擇： 情形一：只包含Ai 情形二：包含Ai和以Ai-1結(jié)尾的最大連續(xù)和序列動(dòng)態(tài)規(guī)劃：轉(zhuǎn)移方程： F(i)=maxAi , F(i-1)+Ai邊界：F(1)=A1要求的結(jié)果為maxF(i)|1=i=n該算法的時(shí)間復(fù)雜度為O(n)一個(gè)簡(jiǎn)化的問(wèn)題例一 算法一枚舉設(shè) F(i)為以Ai結(jié)尾長(zhǎng)度不超過(guò)M的最大子序和ikijjmkAiF1.1|max)( 對(duì)于每個(gè)F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時(shí)間復(fù)雜度為O(n2)原問(wèn)題初步分析簡(jiǎn)化方程ikijjmkAiF1.1|max)(i1jjA) i (S令.1| )(min)(.1| )()(maxmkkiSiSmkki