NOIP實(shí)用算法中國計(jì)算機(jī)學(xué)會(huì)編

1、201 7- 201 8NOI P實(shí)用算法51.模擬方a.用數(shù)學(xué)量和圖形描述問b.模擬計(jì)算過c.模擬時(shí)的優(yōu)d.高精度計(jì)算算匚中玉計(jì)算機(jī)學(xué)會(huì)20172.排序算法與算法時(shí)空復(fù)雜a.簡單排序算b. 快速排序、堆排c.算法時(shí)空復(fù)雜d. 時(shí)空的簡單優(yōu)化方e.線性時(shí)間排f. 歸并排9g.合理選用排序算3. 搜10a.復(fù)雜的模擬問題與利用相似10b. 函數(shù)的遞歸調(diào)10c.棧與深度優(yōu)先搜11d. 深度優(yōu)先搜索的優(yōu)12e.隊(duì)列與廣度優(yōu)先搜12f. 廣度優(yōu)先搜索的優(yōu)12134. 貪心方14a .工程計(jì)劃模14b. 部分背包與每步最14c. 構(gòu)造貪心算15155.動(dòng)態(tài)規(guī)16a.另一種形式的工程計(jì)16b. 記憶化搜1

2、6c .數(shù)字三角形：遞推地思考問17d. 石子合并：狀態(tài)的確17e. 街道問題：狀態(tài)量維數(shù)的確定與無后效18f. 0-1 背包：巧妙地選取狀態(tài)19g. Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方20h. 最長非降子序列模20i. 構(gòu)造動(dòng)態(tài)規(guī)劃算21j. 動(dòng)態(tài)規(guī)劃、遞推、廣度優(yōu)先搜索的區(qū)別與轉(zhuǎn)21216.常用數(shù)學(xué)方.222a.排列組.22b. 遞推與通項(xiàng)的選237. 分26a .子問題與母問題的相似26b. 二分查.26c. 分析算.26d.最長非降子序列的二分298. 圖論思30a. 圖論基.30b. 圖的表示方30c .經(jīng)典圖論算30d. 構(gòu)造圖論模3233附件：關(guān)鍵路徑算法、篝火晚會(huì)問題解法源

3、文331. 模擬方法a. 用數(shù)學(xué)量和圖形描述問題 計(jì)算機(jī)處理的是數(shù)學(xué)量。若要用計(jì)算機(jī)解決實(shí)際問題，需要把實(shí)際問題抽象為數(shù)學(xué) 量，或者數(shù)字。比如， 記事本把文字按 ASCII 碼表轉(zhuǎn)換為數(shù)字儲(chǔ)存起來，極品飛車把賽車的性能表示為數(shù) 字，來權(quán)衡賽車的 好壞。一個(gè)漂亮的算法，需要用數(shù)學(xué)量表示出來。任務(wù)：現(xiàn)有兩個(gè)軟件工程的制作任務(wù)，你的團(tuán)隊(duì)可以接手其中任意一個(gè)?，F(xiàn)要在兩 個(gè)中選擇一個(gè)，需要 考慮制作成本，制作成功的可能性，可獲得經(jīng)濟(jì)收益的多少，對你的團(tuán)隊(duì)知名度的 影響等等因素。你 如何量化地分析和解決這個(gè)問題？ 提示：需要把每一項(xiàng)都轉(zhuǎn)化為數(shù)值，必要時(shí)加入權(quán)值、計(jì)算期望。如果只考慮以上 四個(gè)因素，可以得到

4、 以下數(shù)學(xué)式 綜合收益 = 制作成功的概率 *（ 可獲得經(jīng)濟(jì)收益 -制作成本 ）* 經(jīng)濟(jì)效益的權(quán)值 + 團(tuán)隊(duì)知 名度的影響 * 社會(huì) 效益的權(quán)值 其中概率和兩個(gè)權(quán)值是需要估計(jì)的值。有時(shí)，我們需要用更直觀的圖形來描述實(shí)際問題。圖論就是一個(gè)絕佳的方法。圖是一種表示離散量間關(guān)系的形式，它也是一種思想， 常被用于建模。同時(shí)， 前人也為我們提供了很多現(xiàn)成的圖論算法，能夠解決很多常見問題，這些將在之后 被提到。矩陣也是一種常見的方法。有時(shí)矩陣被表示成三角形的形式，比如 矩陣常常和數(shù)學(xué)有關(guān)， 在計(jì)算機(jī)計(jì)算時(shí)常常利用矩陣的遞推式。這也將在后面被提到。b. 模擬計(jì)算過程 模擬方法是最常見、最直接的算法構(gòu)建方法。

5、楊輝三角”gcd(a,b) )任務(wù)：編程實(shí)現(xiàn)歐幾里得算法(輾轉(zhuǎn)相除法，求兩個(gè)數(shù)的最大公約數(shù) 提示： 歐幾里得算法原理： gcd(a,b)=gcd(b,amodb)歐幾里得算法的圖形描述|16863|16863|2 |42|1. 寫下兩個(gè)數(shù) 2. 將兩數(shù)相除，余數(shù)寫在較大的數(shù)下面1|4221|1|4221|2整除|16863|2|16863|23.將每列最下面的數(shù)相除，余數(shù)寫在被除數(shù)下面 4.重復(fù)步驟 3直至整除，此時(shí)最后寫下的余數(shù)即為 開始時(shí)兩數(shù)的最大公約數(shù) 這是一個(gè)簡單的模擬算法，實(shí)際過程中，量間的關(guān)系往往比這復(fù)雜得多，因而，模 擬算法可以是很復(fù)雜 的。有些模擬算法還涉及到圖形和其他復(fù)雜的數(shù)

6、據(jù)結(jié)構(gòu)，這需要我們熟練地運(yùn)用語言， 巧妙地把其他關(guān)系轉(zhuǎn) 化為數(shù)學(xué)量間關(guān)系。c. 模擬時(shí)的優(yōu)化 如果處理不當(dāng)，模擬方法寫出的程序會(huì)非常長。這要求我們在模擬是將相似的步驟 合為一體，適時(shí)利用 函數(shù)簡化程序。/* 實(shí)現(xiàn)時(shí)，若將左邊一列數(shù)最下面的記為以上面的歐幾里得算法為例：L1000 、右邊一列數(shù)記為 R1000 ，顯然是不明智的，為只有每列最后一個(gè)數(shù)會(huì)在以后的計(jì)算中用到*/* 實(shí)現(xiàn)方法一：及每一列最后一個(gè)數(shù)分別為L、R。輸入即可是L、R,返回gcd(L,R)*/intEuclid_1(intL,intR) for(;)L=L%R;if(L=0)returnR;R=R%L;if(R=0)return

7、L;/* 我們發(fā)現(xiàn)有兩步是相似的。因而我們可以把它簡化為實(shí)現(xiàn)方法二 */ intEuclid_2(intL,intR)intt;for(;) t=R;R=L%R;L=t;if(R=0)returnL;/* 甚至我們可以寫成遞歸形式。以下是實(shí)現(xiàn)方法三 */ intEuclid_3(intL,intR) if(L%R=0)returnR;elsereturnEuclid_3(R,L%R);這個(gè)實(shí)例主要體現(xiàn)模擬算法的簡化過程。雖然在這樣小的程序段中，這樣的簡化作 用不大，但遇到復(fù)雜 的模擬問題，這種利用相似性的簡化便非常有用了。應(yīng)當(dāng)重視這樣的代碼優(yōu)化。d. 高精度計(jì)算算法 競賽中經(jīng)常會(huì)用上一些很大的

8、數(shù)，超出長整型的數(shù)值范圍。這時(shí)我們需要使用高精 度計(jì)算算法。這種算 法可以把數(shù)值范圍增加到我們想要的程度。高精度函數(shù)往往包括加、減、乘、輸入、輸出五種。實(shí)現(xiàn)高精度計(jì)算時(shí)，常常使用模擬算法模擬小學(xué)豎式運(yùn)算。我們把一個(gè)高精度數(shù)表示為一個(gè)數(shù)組 H ，數(shù)組中的某一個(gè)數(shù)相當(dāng)于高精度數(shù)的某一位。要注意的是，輸出時(shí)往往要求以十進(jìn)制形式輸出。因而，高精度數(shù)每一位都應(yīng)便于 直接輸出。這樣，每一位上的最大數(shù)都應(yīng)是10八n-1。簡單地說，若把H定為unsigned型，高精度數(shù) 每一位上最大數(shù) 最好為 9999 。這樣既能盡量利用儲(chǔ)存空間，又便于輸出。另外，高精度數(shù)有時(shí)會(huì)用到負(fù)數(shù)。在補(bǔ)碼的體系中，仍然可以按正數(shù)的方法

9、處理負(fù) 數(shù)，但是要特別注意 輸出時(shí)的問題，和對溢出的防止。任務(wù)：實(shí)現(xiàn)高精度運(yùn)算加法，從末提示：設(shè)計(jì)函數(shù)unsigned*HAdd(unsignedN1,unsignedN2,unsignedAns)位起相加，注意是否進(jìn)位。顯然，減法作為加法的逆運(yùn)算，也很容易實(shí)現(xiàn)。另一種聰明的辦法是，對減數(shù)每一 位取補(bǔ)碼，在做加法5即可。請讀者自行實(shí)現(xiàn)高精度減法。高精度乘法困難一些。我推薦的方法是，先考慮多位高精度數(shù)乘一位高精度數(shù)的過 程。多位高精度數(shù)乘 多位高精度數(shù)可以轉(zhuǎn)化為多位高精度數(shù)乘另一高精度數(shù)每一位，再將結(jié)果相加的過 程。下面給出多位 高精度數(shù)乘一位高精度數(shù)的源代碼：/*N1 為多位高精#define

10、H_Bit256/* 定義常數(shù)：高精度數(shù)位數(shù) */ unsigned*HTimesInt(unsignedN1,intN2,unsignedAns)度數(shù)，N2為高精度數(shù)的一位，An s為另一高精度數(shù)，用于儲(chǔ)存結(jié)果 */ /*這里允許N1與Ans相同*/ unsignedi,up=0;unsignedlongtemp;for(i=H_Bit-1;i<=H_Bit;i-) temp=N1i*N2+up;up=temp/10000;Ansi=(unsigned)(temp%10000);returnAns;/* 函數(shù)返回作為答案的高精度數(shù)首地址，這樣更便于高精度運(yùn)算函數(shù)的使用，例如連乘可以寫成

11、HTimesInt(HTimesInt(N1,N2,Ans),N3,Ans)*/高精度數(shù)的輸入輸出需要專門的函數(shù)。針對不同語言的不同特點(diǎn)，可以比較容易地 寫出這兩個(gè)函數(shù)。但 要注意輸出非首位數(shù)位上的 “0” 。習(xí)題模擬方法的習(xí)題6感謝深藍(lán)評測系統(tǒng)提供習(xí)題2. 排序算法與算法時(shí)空復(fù)雜度a. 簡單排序算法簡單排序算法包括冒泡排序、插入排序、選擇排序。這三種算法容易理解、編寫方 便，適用于數(shù)據(jù)規(guī)模 較小的情形。冒泡排序( BubbleSort )的基本思路是：(以從小到大排序?yàn)槔?從前到后逐個(gè)比 較相鄰兩數(shù)，若前 數(shù)大于后數(shù)，就將兩數(shù)交換。不斷重復(fù)這一過程，直至全部數(shù)字已按從小到大排好。考慮到實(shí)用性

12、的問題，插入排序和選擇排序這里不再介紹。對于NOIP提高組而言，這些算法時(shí)間復(fù)雜度過高，很難應(yīng)付較大的數(shù)據(jù)規(guī)模。建議 盡量不要采用簡單 排序算法，除非你十分確信數(shù)據(jù)規(guī)模在可承受范圍之內(nèi)。b. 快速排序、堆排序 快速排序和堆排序是比簡單排序快的排序算法，在競賽中常常被采用。這里，我們 介紹快速排序算法。堆排序的實(shí)現(xiàn)不作介紹，若想了解，可咨詢谷歌或百度?？焖倥判? QuickSort )基于分治思想。它的基本思路是：(以從小到大排序?yàn)槔? 取一個(gè)數(shù)作為標(biāo) 記元素，將比它大的數(shù)放在它右側(cè)，比它小的數(shù)放在它左側(cè)，再通過遞歸的方法， 將左側(cè)的數(shù)用以上 的方法排好，右側(cè)的數(shù)也用以上的方法排好即可。面這個(gè)視

13、頻能很直觀地比較冒泡排序 (BubbleSort )和快速排序 (QuickSort )： 在數(shù)據(jù)規(guī)模很大時(shí)，平均情況下快排比冒泡快很多。 在處理NOIP提高組含排序的問 題時(shí)，一般要選擇 快速排序或堆排序。面將介紹快速排序的實(shí)現(xiàn)(以從小到大排序?yàn)槔?。快排運(yùn)用分治思想，因而要用函數(shù)的遞歸調(diào)用來實(shí)現(xiàn)：voidQuickSort(inta,intst,intstp)/ 這里也可以定義成 voidQuickSort（int*st,intlen)。為了便于理解，我使用前一種寫法。intmid;mid=partition(a,st,stp);/partition()用于確定標(biāo)記元素的位置。if(lmi

14、d-1)QuickSort(a,st,mid-1);if(mid+1r)QuickSort(a,mid+1,stp);現(xiàn)在的關(guān)鍵問題在于如何寫 partition（）寫法一：對于數(shù)列 567538162 1.取首個(gè)元素做標(biāo)記元素，取出它，令指針 p 指向最右邊的數(shù)的右邊67538162p-5；否5；否2.將p向左移動(dòng)到小于標(biāo)記元素的數(shù)（或空缺處）為止。若指向空缺，貝y跳到貝將該數(shù)和 p 移到 空缺處 p-26753816_3. 將P向右移動(dòng)到大于標(biāo)記元素的數(shù)（或空缺處）為止。若指向空缺，貝y跳到貝將該數(shù)和 p 移到 空缺處 2_753816p-64. 重復(fù) 2和3。2p-17538_66 21

15、_538p-766721p-35_87665.把標(biāo)記元素放入空格處2135p-58766寫法二：寫法二比寫法一短一些，但理論上講，寫法二要慢一些（因?yàn)樗髻x值運(yùn) 算多一些）。下面給出源代碼與分析：voidQuickSort(longa,longst,longstp)/ 這里將 partition()結(jié)合進(jìn)QuickSort()中l(wèi)ongt,n,l,r;n=ast;l=st+1;r=stp;/ 從右找，找到一個(gè)小于標(biāo)記元素的數(shù)for(;)for(;al=n&l=n&rst;r-);/ 從左找，找到一個(gè)大于標(biāo)記元素的數(shù)if(l=r) break ;/ 如果 l在 r 右側(cè)，則跳出t=al;al=a

16、r;ar=t;/ 交換，使小于標(biāo)記元素的在左，大于標(biāo)記元素的在右ast=ar; / 取出最右側(cè)的小于標(biāo)記元素的數(shù)寫入空缺ar=n; / 空缺處放入標(biāo)記元素if(r-st1)QuickSort(a,st,r-1);if(stpl)QuickSort(a,l,stp);以上快排實(shí)現(xiàn)方法的最差情形是排列整齊的情況，這時(shí)它的運(yùn)行效率會(huì)很低。為了 解決排列整齊的情形， 我們可以使用隨機(jī)快速排序法，即隨機(jī)選取一個(gè)數(shù)作為標(biāo)記元素（實(shí)現(xiàn)時(shí)，將其與 第一個(gè)數(shù)交換即可）。c. 算法時(shí)空復(fù)雜度 為了描述一個(gè)算法的優(yōu)劣，我們引入算法時(shí)間復(fù)雜度和空間復(fù)雜度的概念。時(shí)間復(fù)雜度：一個(gè)算法主要運(yùn)算的次數(shù)，用 O（） 表示。通

17、常表示時(shí)間復(fù)雜度時(shí)，我們只保留影響最大的項(xiàng)，并忽略該項(xiàng)的系數(shù)。例如主要運(yùn)算為賦值的算法，賦值做了 3n八3+n八2+8次，則認(rèn)為它的復(fù)雜度為0（n八3）;若主要運(yùn)算為比較，比較做了 4*2八n+2*n八4+700次，由于數(shù)據(jù)很大時(shí)，指數(shù)級(jí)增長的25影響 最大，我們認(rèn)為它 的時(shí)間復(fù)雜度為0（2八n）。常見的時(shí)間復(fù)雜度有下列幾個(gè)：0（n） 貪心算法多數(shù)情況下為此時(shí)間復(fù)雜度0（nlbn）有時(shí)帶有分治思想的算法的時(shí)間復(fù)雜度（注Ibn表示以2為底的n的對數(shù)）0（n 八2）有時(shí)動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度0（n 八3）有時(shí)動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度0（2八 n）有時(shí)搜索算法的時(shí)間復(fù)雜度0（n!） 有時(shí)搜索算法的時(shí)間復(fù)雜

18、度 有時(shí)時(shí)間復(fù)雜度中含有兩個(gè)或多個(gè)字母，比如遍歷一個(gè) m*n 的矩陣，時(shí)間復(fù)雜度為0（m*n） 。要注意的是，時(shí)間復(fù)雜度相同的兩個(gè)算法，它的實(shí)際執(zhí)行時(shí)間可能會(huì)有數(shù)倍的差距， 因而實(shí)現(xiàn)時(shí)要特別 注意細(xì)節(jié)處的優(yōu)化。8N0IP提高組執(zhí)行時(shí)限常常為1s。一般認(rèn)為，將數(shù)據(jù)規(guī)模代入到時(shí)間復(fù)雜度，若所得值小于或接近于1000000 ，就是絕對安全的、不超時(shí)的。例如，0(n八2)的動(dòng)態(tài)規(guī)劃算法，可承受的數(shù)據(jù)規(guī)模是 nW 1000 ; 0(2八n)的搜索算法，可承受的數(shù)據(jù)規(guī) 模是nW20 ; 0(n!)的搜索算法，可承受的數(shù)據(jù)規(guī)模是nW9。實(shí)際上，以現(xiàn)在的 CPU 運(yùn)行速度， 5000000 也應(yīng)該不成問題?？?/p>

19、間復(fù)雜度：一個(gè)算法消耗儲(chǔ)存空間(內(nèi)存)的大小，用 0()表示?？臻g復(fù)雜度的表示規(guī)則與時(shí)間復(fù)雜度類似。在實(shí)際應(yīng)用時(shí)，空間的占用是需要特別注意的問題。太大的數(shù)組經(jīng)常是開不出來的， 即使開出來了，遍 歷的時(shí)間消耗也是驚人的。面我們簡單地分析一下簡單排序算法、快速排序、堆排序的時(shí)空復(fù)雜度。這三種算法都是基于比較的排序算法，以比較次數(shù)作為主要運(yùn)算。簡單排序算法最差時(shí)需做n“2次比較，平均情況下時(shí)間復(fù)雜度通常被認(rèn)為是0(n 八2)?？焖倥判蜃畈顣r(shí)需做n八2次比較，可以證明平均情況下需做nlbn次比較，時(shí)間復(fù)雜 度是 0(nibn)。堆排序時(shí)間復(fù)雜度是 0(nibn) ?？臻g上，三者都不需要額外開辟暫存數(shù)組

20、，快排遞歸調(diào)用時(shí)需要使用稍多一些的儲(chǔ) 存空間。綜合來看，快速排序、堆排序優(yōu)于簡單排序算法。另外，可以證明基于比較的排序算法時(shí)間復(fù)雜度下界為 O（nlbn） 。d. 時(shí)空的簡單優(yōu)化方法 時(shí)間上的優(yōu)化在于少做運(yùn)算、做耗時(shí)短的運(yùn)算等。有幾個(gè)規(guī)律需要注意： 整型運(yùn)算耗時(shí)遠(yuǎn)低于實(shí)型運(yùn)算耗時(shí)。+ 、 - 運(yùn)算非常快（減法是將減數(shù)取補(bǔ)碼后與被減數(shù)相加，其中位運(yùn)算更快一些，但 是減法也比加法稍 慢些。）*運(yùn)算比加法慢得多 / 運(yùn)算比乘法慢得多 比較運(yùn)算慢于四則運(yùn)算賦值運(yùn)算慢于比較運(yùn)算（因?yàn)橐獙憙?nèi)存）這些規(guī)律我們可以從宏觀上把握。事實(shí)上，究竟做了幾步運(yùn)算、幾次賦值、變量在內(nèi)存還是緩存等多數(shù)由編譯器、系統(tǒng)決定。但

21、是，少做運(yùn)算（尤其在循環(huán)體、遞歸體中）一定能很大程度節(jié)省時(shí)間。面來舉一個(gè)例子：計(jì)算組合數(shù)C(m,n)n件物品取出m件的組合數(shù)。C(m,n) 可用公式直接計(jì)算。 C(m,n)=n!/(n-m)!m!)C(m,n)=n(n-1)(n-2)(nm+1)/(n-m)!。顯然，有時(shí)所作的乘法少很多，會(huì)快一些?？墒沁@樣算真的最快嗎？另一條思路是 C(m,n)=C(m,n-1)+C(m-1,n-1)，遞推下去，直到可利用C(1,k)=k=C(k-1,k) 為止。我覺得這種只用加法的運(yùn)算會(huì)快些，盡管加法多一些。(我沒試驗(yàn)過，你可以去試一下。)空間上的優(yōu)化主要在于減小數(shù)組大小、降低數(shù)組維數(shù)等。常用的節(jié)省內(nèi)存的方

22、法有：壓縮儲(chǔ)存 例：數(shù)組中每個(gè)數(shù)都只有 0、1兩種可能，則可以按位儲(chǔ)存，空間壓縮為原來的八分之一。覆蓋舊數(shù)據(jù) 例：矩陣中每一行的值只與上一行有關(guān)，輸出只和最末行有關(guān)，則可將奇數(shù)行儲(chǔ)存在第一行，偶數(shù)行儲(chǔ)存在第二行，降低空間復(fù)雜度。要注意的是，對空間的優(yōu)化即使不改變復(fù)雜度、只是改變n的系數(shù)也是極有意義的。空間復(fù)雜度有時(shí)對時(shí)間也有影響，要想方設(shè)法進(jìn)行優(yōu)化。e. 線性時(shí)間排序基于比較的排序算法時(shí)間復(fù)雜度下界為 O(nlbn) 。因而，若還要降低復(fù)雜度，要放棄基于比較的排序9算法。有一類排序算法叫做線性時(shí)間排序，它們的時(shí)間復(fù)雜度為O(n) 。下面介紹一種。計(jì)數(shù)排序思路：開辟暫存數(shù)組b , bk表示欲排序

23、數(shù)組a中k出現(xiàn)的次數(shù)(需要遍歷 a )，最后遍歷b，可將a排好。這種想法非常簡單，實(shí)現(xiàn)也很容易。事實(shí)證明，在 a 取值范圍很?。ㄈ缯头秶?時(shí)，它是很高效的 排序算法，比快排快不少?？墒?a 取值范圍較大（如長整型范圍）時(shí)，它的執(zhí)行時(shí) 間會(huì)變長，而且 數(shù)組 b 有時(shí)開不出來。實(shí)際上計(jì)數(shù)排序時(shí)間復(fù)雜度為 O（n+m） ，空間復(fù)雜度也為 O（n+m） ，m 表示 a 取值 范圍。若 m 很大， 則也不能在時(shí)限內(nèi)執(zhí)行完。f. 歸并排序 有一種排序時(shí)極為常見的情形：有一張成績表，記錄著許多學(xué)生的成績，要將他們 按成績排序，但成績 相同者的相對順序不能改變。換句話說，ABCDE五人，A、C、D成績相同

24、，顯然排序完之后會(huì)排在一起，現(xiàn)在的 要求是：他們排在一 起的順序也必須是ACD，不能是ADC、CAD- 這樣的實(shí)際問題涉及到排序的穩(wěn)定性。排序的穩(wěn)定性：一個(gè)排序算法，若可使排序前后關(guān)鍵字相同的項(xiàng)相對順序不變，則 稱該排序算法是穩(wěn)定 的排序算法。面我們來考察常見排序算法的穩(wěn)定性。在編寫合理的情況下，簡單排序算法是穩(wěn)定的；快速排序、堆排序是不穩(wěn)定的（你 可以好好想想這是為 什么）。在NOIP中，往往排序是沒有附帶其他項(xiàng)目的，也就不要求排序穩(wěn)定?？焖倥判颉⒍?排序仍然是最佳選 擇?？墒怯袥]有時(shí)間復(fù)雜度為 O（nlbn） 的穩(wěn)定的排序算法呢？有的。歸并排序基于分治思想：把要排序的數(shù)組平分兩半，對兩部分

25、分別排序（遞歸地） 后再合并起來。合并 時(shí)，將一個(gè)數(shù)組按順序插入另一個(gè)數(shù)組中，需要開辟一個(gè)暫存數(shù)組。利用空間優(yōu)化， 可只用開辟一個(gè) 與原數(shù)組等大的數(shù)組。歸并排序的源代碼會(huì)放在本章的附件中。請讀者自己研究。歸并排序的優(yōu)缺點(diǎn)都很明顯。 無論情形如何，它的比較次數(shù)、賦值次數(shù)都穩(wěn)定在 nlbn ， 沒有最差情況， 運(yùn)行時(shí)間與快速排序、堆排序相當(dāng)。而且，它是穩(wěn)定的排序算法。但是，它的內(nèi)存占用回達(dá)到快速排序、堆排序的兩倍，競賽時(shí)使用容易造成內(nèi)存超 出限制。NOIP初賽曾考察過歸并排序。問題大意是：找出一個(gè)算法，使五個(gè)數(shù)在n次比較（兩兩比較）后一定 能排定次序，求n的最小值。在快速排序、堆排序的最差情況下，

26、需要 10 次、 9次比較?？墒牵褂脷w并排序只需要7次！記?。簹w并 排序沒有最差情況。g. 合理選用排序算法面是本章講過的排序算法的優(yōu)缺點(diǎn)比較：（這里只講最主要的） 排序算法時(shí)間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)簡單排序0(n八2)編寫方便執(zhí)行時(shí)間長 快排0(nibn)執(zhí)行時(shí)間短很差情況下執(zhí)行時(shí)間長、占用內(nèi)存多 堆排序 0(nlbn) 執(zhí)行時(shí)間短編寫有點(diǎn)麻煩，有較差的情況 計(jì)數(shù)排序 0(n+m) 編寫方便，取值范圍小時(shí)很高效取值范圍大時(shí)效率低、易超內(nèi)存 限制 歸并排序 0(nibn) 穩(wěn)定的排序算法，無較差情況占用內(nèi)存很大 競賽中首選快速排序、堆排序。但有時(shí)也應(yīng)比較各排序的優(yōu)缺點(diǎn)，依實(shí)際合理選用。習(xí)題 排序的習(xí)

27、題 感謝深藍(lán)評測系統(tǒng)提供習(xí)題103. 搜索a. 復(fù)雜的模擬問題與利用相似性 在講模擬方法時(shí)我們講過利用相似性來簡化算法?，F(xiàn)在，我們繼續(xù)關(guān)注這個(gè)問題。搜索算法是一種 “模擬”思維的算法，比較接近平常的思維。與模擬算法相比，它 更深刻地利用了相似性。為了更好地說明，下面舉一個(gè)例子： 有一把有n位字母的密碼鎖，每一位上的字母都可從a到Z選取?，F(xiàn)密碼被遺忘，開鎖 時(shí)，請給出一個(gè) 方便的方法，使每個(gè)字母組合都被嘗試過。最容易想至y的方法便是，按 aaaa , aaab , aaac , ，aaaz , aaba , -ZZ zy ZZ Z這樣的字典序來嘗試。我們可以這樣考慮：先選定第一位，再選定第二位，

28、直到選定第n位，形成一個(gè)完整的字母組合。具體地，在每一位的選取時(shí)，都從a開始，到后面位的字母組合全部嘗試過，再跳到 下一個(gè)字母；若（非 首位）已經(jīng)跳到z而還需再跳一個(gè)字母時(shí)，就跳到a，同時(shí)讓它的前一位跳到下一個(gè) 字母。例如， n=3 時(shí)，形成的字母組合的順序是aaa-aaa b-aab c-aac z-aaz ba-aba b-abb z-abz ca-aca zz-azz baa-baa zz-bzz caa-caa zzz-zzz以上描述的是一種常見的遍歷方法。我們注意到，選定每一位的過程是極其相似的。我們需要利用這種相似性。b. 函數(shù)的遞歸調(diào)用 結(jié)構(gòu)化編程語言提供的最大好處無疑是函數(shù)的遞

29、歸調(diào)用。如果把函數(shù)看成解決某個(gè)問題的過程，那么遞歸就可以看成把問題變成相似而更小 的問題的過程。注意 這兩個(gè)關(guān)鍵詞：相似、更小。遞歸的本質(zhì)是利用相似性。我們接著講上面提到的密碼鎖問題?，F(xiàn)在我們要把嘗試過的字母組合都輸出到屏幕 上。我們用遞歸法來完成這個(gè)過程。寫遞歸體一般分為兩步：把大問題化成小問題、解 決最小問題。charstring1000,n;voidcode(intLeft) / 遞歸體， Left 表示還需要決定的位數(shù)，這個(gè)值隨問題的減小而遞減。11if(Left=1) / 把大問題化成小問題for(stringn-Left=a;stringn-Left456 63878思路：每次將一

30、個(gè)構(gòu)型變?yōu)榱硪粋€(gè)，再遞歸地檢查后者能否到達(dá)目標(biāo)構(gòu)型。時(shí)間復(fù) 雜度0（4八n）。偽代碼：intEightNumbers（構(gòu)型 ）這里返回步驟數(shù)，若需要知道具體步驟，則用另用棧儲(chǔ)存步驟。同源構(gòu)型則返回 32767同目標(biāo)構(gòu)型則返回 0 step=n1-4 最小值n1=EightNumbers(變化出的構(gòu)型1)n2=EightNumbers(變化出的構(gòu)型2)n3=EightNumbers(變化出的構(gòu)型3)n4=EightNumbers(變化出的構(gòu)型 4）step 為32767 則返回 32767返回 step+1d. 深度優(yōu)先搜索的優(yōu)化 顯然，以上代碼是可以優(yōu)化的。深搜的優(yōu)化過程也叫 “剪枝 ” ?？?/p>

31、慮到實(shí)用性，這 里我們只講最簡單的剪 枝方法。對于上面的偽代碼，將 “同源構(gòu)型則返回 32767” 改為 “同已查找構(gòu)型則返回32767 ”就可以顯著提高效率。但是這里需要開辟一個(gè)數(shù)組（棧），記錄之前 “經(jīng)過”的構(gòu)型。如果想避免遍歷數(shù) 組，可以做成哈希表， 而且要壓縮儲(chǔ)存才行。還有的簡單方法，編寫的時(shí)候自然會(huì)想到的。關(guān)鍵是要權(quán)衡，用這樣的方法所增加 的編寫難度是否配得 上所節(jié)省的運(yùn)行時(shí)間。編寫難度增大，調(diào)試的難度也會(huì)增大哦。e. 隊(duì)列與廣度優(yōu)先搜索 上面講過用棧來非遞歸地實(shí)現(xiàn)深搜。若是把棧改成隊(duì)列呢？ 經(jīng)過分析，你會(huì)發(fā)現(xiàn)，這樣修改后深搜變成了廣搜！ 用這樣的方法可以實(shí)現(xiàn)廣搜。用數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)避

32、免大量元素的移動(dòng)。 實(shí)現(xiàn)時(shí)， 可以先算出隊(duì)列元素的上限 max ， 開辟 amax ，并 設(shè)ast為隊(duì)列起始（st初值為0），隊(duì)列的第i項(xiàng)儲(chǔ)存在a（st+i-1）%max。這樣，出隊(duì)列只用將 st=（+st%max） 即可。要注意的問題是，廣搜類似于遞推，往往需要開辟空間儲(chǔ)存每一步 “遞推 ”所得到 的值。f. 廣度優(yōu)先搜索的優(yōu)化 廣度優(yōu)先搜索比較容易優(yōu)化，運(yùn)行時(shí)間往往比深搜短一些（不過內(nèi)存占用比深搜大 得多）。另外，廣搜 有時(shí)可以清晰地反映搜索深度。若上面的八數(shù)碼問題改為 “現(xiàn)要求找出一種方法，使呈現(xiàn)目標(biāo)構(gòu)型經(jīng)過的對調(diào)步數(shù) 最少”，則用廣搜更好。13廣搜常用的優(yōu)化方法： 哈希表法 記錄隊(duì)列中

33、已有節(jié)點(diǎn)，用于判斷是否需要擴(kuò)展節(jié)點(diǎn)。A*算法一一構(gòu)造估價(jià)函數(shù)。雙向廣度優(yōu)先搜索從源節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)一起開始搜索。由于NOIP提高組近年來幾乎不出搜索題； 可用搜索的題目，由于搜索時(shí)間復(fù)雜度太 高，數(shù)據(jù)規(guī)模太大， 搜索只能得部分分?jǐn)?shù)。加之搜索思路較簡單，搜索法這里不再詳細(xì)敘述。若想了解， 大家可以用搜索 引擎搜索。習(xí)題 搜索的習(xí)題 感謝深藍(lán)評測系統(tǒng)提供習(xí)題144. 貪心方法a. 工程計(jì)劃模型 我們常常碰到這樣的問題：完成一個(gè)工程需要若干個(gè)步驟，每個(gè)步驟都有若干種方 法，圖示 步驟a步驟b步驟c.步驟n 方法b1方法c1 方法a1方法b2方法c2方法n1 方法a2方法b3方法c3 方法c4 每個(gè)方法

34、有一個(gè)權(quán)值（如效率、質(zhì)量），其大小往往和其他步驟中選取的方法有關(guān)。有些時(shí)候權(quán)值無意 義，表示方法不可選擇。要求給出一個(gè)方法組合，是權(quán)值和最大。在這里，暫且把它稱作 “工程計(jì)劃 ”。很多實(shí)際問題都可以歸納為這個(gè)模型。時(shí)間復(fù)雜對于不同形式的工程計(jì)劃，我們有不同的解法。若權(quán)值與整個(gè)過程或前后步驟的方法選擇都有關(guān)，我們使用搜索算法 度高得嚇人。若每個(gè)權(quán)值只與上（或下）一步或少數(shù)幾步的方法選擇都有關(guān)，我們使用動(dòng)態(tài)規(guī)劃有比較高的效率， 在下一章會(huì)講到。若每個(gè)權(quán)值與其他步驟的方法選擇都沒有關(guān)系，我們使用貪心方法。b. 部分背包與每步最優(yōu) 強(qiáng)調(diào)：每個(gè)權(quán)值與其他步驟的方法選擇都沒有關(guān)系。這樣每步最優(yōu)就可以得到全

35、局 最優(yōu) 每一步都取最 大的權(quán)值就可以了。換而言之，貪心算法要求，局部的貪心選擇，可以組成全局的最優(yōu)解。在實(shí)際問題中，這是需要證明的。如果這個(gè)無法證明，貪心算法所得的解不是最優(yōu) 解，一般只是較優(yōu)解較優(yōu)解可為搜索剪枝提供方便）。面是貪心算法最經(jīng)典的例子： 部分背包問題。下一章會(huì)講到另外兩種背包問題。 ）問題：有N件物品和一個(gè)最大載重為M的背包,每件物品都有相應(yīng)的重量和價(jià)值?，F(xiàn)要求給出一個(gè)存放方案，使背包中物品總價(jià)值最大。部分背包要求，每件物品都可只裝入它的一部分部分重量有成比 例的部分價(jià)值）。所涉及到的數(shù)字均為整數(shù)。注：有時(shí)該問題表述為體積形式，即背包體積有限，每件物品有體積和價(jià)值。在 本系列我

36、選擇表述為重量形式。） 思路：背包中物品總價(jià)值最高，即單位重量物品價(jià)值最高。顯然，應(yīng)該多裝單位重 量價(jià)值高的物品。這 樣，我們先裝入單位重量價(jià)值最高的物品， 再裝入第二高的直到重量達(dá)到M （有 必要時(shí)最后一件物 品只裝一部分），已達(dá)到物品總價(jià)值最高。這個(gè)證明應(yīng)該很嚴(yán)謹(jǐn)吧 該算法時(shí)間復(fù)雜度 O（n） ，效率很高；而且實(shí)現(xiàn)很容易。這些是貪心法最大的特點(diǎn)。很多競賽題看似可以用貪心法，其實(shí)貪心法得不到最優(yōu)解，原因是每一步的選擇對 其他步驟有影響。數(shù)字三角形問題：有一個(gè)數(shù)字三角形（如下圖）?，F(xiàn)有一只螞蟻從頂層開始向下走， 每走下一級(jí)時(shí)，可 向左下方向或右下方向走。求走到底層后它所經(jīng)過的數(shù)的最大值。63

37、826 2165 32476如果用貪心法，每次向最大的方向走，得到結(jié)果為 1+6+8+2+3=20 ?？墒敲髅鬟€ 有另一條路，1+3+6+6+7=23 。15問題出在哪？每次的選擇對后面的步驟會(huì)有影響！第三級(jí)選了8，就選不到第四、五級(jí)較大的數(shù)了。這個(gè)問題正確的解法會(huì)在下一章介紹。有一個(gè)很實(shí)用的小技巧：競賽題會(huì)給出數(shù)據(jù)規(guī)模。通過數(shù)據(jù)規(guī)模，我們可以大致判 斷該用何種算法。貪 心算法可承受的數(shù)據(jù)規(guī)模很大， 一般都會(huì)上萬。 如果給出的數(shù)據(jù)規(guī)模是 100或1000 ， 優(yōu)先考慮動(dòng)態(tài)規(guī) 劃吧。c. 構(gòu)造貪心算法 構(gòu)造與證明是貪心算法的難點(diǎn)，常常要求我們要有敏銳的觀察力、多角度思考的變 通能力、豐富的數(shù)學(xué)

38、知識(shí)和推理能力。面舉幾個(gè)貪心算法的例子，供大家揣摩、掌握規(guī)律。刪數(shù)問題：給出一個(gè)N位的十進(jìn)制高精度數(shù)，要求從中刪掉 S個(gè)數(shù)字（其余數(shù)字相對位置不得改變）， 使剩余數(shù)字組成的數(shù)最小。算法構(gòu)造：1.每次找出最靠前的這樣的一對數(shù)字兩個(gè)數(shù)字緊鄰， 且前面的數(shù)字大于后面的。刪除這對數(shù)字中靠前 的一個(gè)。2.重復(fù)步驟1，直至刪去了 S個(gè)數(shù)字或找不到這樣的一對數(shù)。3.若還未刪夠S個(gè)數(shù)字，則舍棄末尾的部分?jǐn)?shù)字，取前 N-S個(gè)。證明思路：顯然，在只刪一個(gè)數(shù)字時(shí)，唯有步驟 1 的方法能使數(shù)變??；可推理得出， 刪多個(gè)數(shù)字時(shí)，所 有最優(yōu)的方法都可看做是對步驟 1的重復(fù)。也就是說，以上方法是最優(yōu)策略之一。在文末的附件中給

39、出了這個(gè)算法的源代碼。工序問題：n件物品，每件需依次在A、B機(jī)床上加工。已知第i件在A、B所需加工時(shí) 間分別為 Ai 、Bi ，設(shè)計(jì)一加工順序，使所需加工總時(shí)間最短。算法構(gòu)造：1.設(shè)置集合F、M、S:先加工F中的，再加工M中的，最后加工S中的。2.對第i件，若AiBi，則歸入S;若Ai=Bi，則歸入M 。3.對F中的元素按Ai升序排列，S中的按Bi降序排列。證明思路：1.F中的能“拉開” A、B加工同一件工件的結(jié)束時(shí)刻，為后面的工件加工“拉開時(shí) 間差 ” ，利于節(jié)省總時(shí) 間。S中的剛好相反。因而，F(xiàn)中元素放在最前一定是最優(yōu)策略之一。2.F中Ai小的前置，可以縮短開始時(shí)B的空閑時(shí)間，但會(huì)使F所有

40、工件“拉開的時(shí)間差”縮短。不過可以證明，后者帶來的損失不大于前者獲得的優(yōu)勢。對稱地，對S也一樣。因而步驟 3 是可行的。種樹問題：一條街道分為n個(gè)區(qū)域（按1-n編號(hào)），每個(gè)都可種一棵樹。有m戶居民, 每戶會(huì)要求在區(qū) 域i-j區(qū)間內(nèi)種至少一棵樹。現(xiàn)求一個(gè)能滿足所有要求且種樹最少的方案。算法構(gòu)造：1.對于要求，以區(qū)間右端（升序）為首要關(guān)鍵字，左端（升序）為次要關(guān)鍵字排序。2.按排好的序依次考察這些要求，若未滿足，則在其最右端的區(qū)域種樹，這時(shí)可能會(huì)滿足多個(gè)要求。證明思路：解法并不唯一， 關(guān)鍵是證明沒有比該解法更好的解法。 按步驟1 排序之后， 會(huì)發(fā)現(xiàn)對于每個(gè)要求，在最右邊的區(qū)域內(nèi)種樹所得的結(jié)果總不會(huì)

41、差于在其他區(qū)域種樹。至于為什么 這樣排序，留給你讀者們思考吧。在文末的附件中給出了這個(gè)算法的源代碼。習(xí)題貪心方法的習(xí)題感謝深藍(lán)評測系統(tǒng)提供習(xí)題165. 動(dòng)態(tài)規(guī)劃a. 另一種形式的工程計(jì)劃b. 記憶化搜索c. 數(shù)字三角形：遞推地思考問題d. 石子合并：狀態(tài)的確定e. 街道問題：狀態(tài)量維數(shù)的確定與無后效性f. 0-1 背包：巧妙地選取狀態(tài)量g. Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方式h. 最長非降子序列模型i. 構(gòu)造動(dòng)態(tài)規(guī)劃算法j. 動(dòng)態(tài)規(guī)劃、遞推、廣度優(yōu)先搜索的區(qū)別與轉(zhuǎn)化a. 另一種形式的工程計(jì)劃 上一章我們講過， 若工程計(jì)劃問題中某一步權(quán)值只和上一步或少數(shù)幾步的選擇有關(guān)， 我們可以使用效率

42、較高的動(dòng)態(tài)規(guī)劃算法?？聪旅孢@個(gè)問題：4-9/ 1-2-5-3-1 / 1-7-8上圖的數(shù)字間連了線。現(xiàn)要從最左邊的 “1” 走到最右邊的 “1” ，每次都只能沿線 向右走到右邊一列的某 個(gè)數(shù)上，要求找出一條路徑，路徑上的五個(gè)數(shù)之和最大。當(dāng)然我們可以把這理解為工程計(jì)劃問題的一種形式。這里，每一步的選擇與上一步相關(guān)；似乎也與前面幾步的選擇有關(guān)，但是注意，前 幾步的影響都可以表 現(xiàn)在上一步上，上一步方法的選擇已經(jīng)可以獨(dú)立決定這一步每種選擇的權(quán)值。此處 適用動(dòng)態(tài)規(guī)劃。換句“專業(yè)”點(diǎn)的話，這里滿足 “無后效性原則 ”，即之后過程不受之前具體過程 的影響。這在后面會(huì)具體 說明。b. 記憶化搜索 再講動(dòng)態(tài)規(guī)

43、劃之前，我們先接觸一下記憶化搜索。注意到，在深度優(yōu)先搜索中，用于遞歸的函數(shù)cal(有時(shí)會(huì)被用同樣的參數(shù)調(diào)用多次。你可能很容易 想到，如果在第一次調(diào)用時(shí)把參數(shù)和對應(yīng)的函數(shù)值儲(chǔ)存起來，若以后再以同樣的參 數(shù)調(diào)用，就不用執(zhí) 行遞歸函數(shù)，直接取出所得的值，不是快得多？ 如果你能想到這些，你就已經(jīng)學(xué)會(huì)記憶化搜索了。事實(shí)上，記憶化搜索能大幅提高效率的地方，往往是在動(dòng)態(tài)規(guī)劃的題目中。動(dòng)態(tài)規(guī)劃能解決的問題，往往可以用記憶化搜索替代動(dòng)態(tài)規(guī)劃解決。如果你實(shí)在無 法掌握動(dòng)態(tài)規(guī)劃，你 可以選擇使用記憶化搜索。不過你要注意以下事實(shí)： 動(dòng)態(tài)規(guī)劃程序?qū)崿F(xiàn)較容易，程序段短，便于調(diào)試；記憶化搜索實(shí)現(xiàn)就比較繁瑣。雖然記憶化搜索可

44、以把時(shí)間復(fù)雜度降低到動(dòng)態(tài)規(guī)劃的水平，但是實(shí)際執(zhí)行時(shí)間會(huì)大 于動(dòng)態(tài)規(guī)劃，甚至有 幾倍到十幾倍的差距。這里不給出記憶化搜索的代碼了。我們還是首選動(dòng)態(tài)規(guī)劃吧17c. 數(shù)字三角形：遞推地思考問題 上一章中我們講過數(shù)字三角形問題： 有一個(gè)數(shù)字三角形（如下圖）。現(xiàn)有一只螞蟻從頂層開始向下走，每走下一級(jí)時(shí)， 可向左下方向或右下 方向走。求走到底層后它所經(jīng)過的數(shù)的最大值。63 826 2165 32476對于這個(gè)問題，貪心法得不到最優(yōu)解，搜索法效率太低。我們知道，深度優(yōu)先搜索 利用了遞歸式的思維， 動(dòng)態(tài)規(guī)劃中，我們使用遞推式的思維。遞歸：要知道第五層時(shí)的最大值，就要知道第四層時(shí)的最大值；要知道第四層時(shí)的三層時(shí)

45、的最大值 而每一步推導(dǎo)的方法是相似的。遞推：知道第一層的最大值，就能知道第二層的最大值，也就能知道第三層的最大 值而每一步推導(dǎo)的 方法是相似的。對比之下，遞推思維不是從結(jié)論入手的，有時(shí)容易失去方向；但是有時(shí)卻可以有很 高的效率。動(dòng)態(tài)規(guī)劃和普通遞推的區(qū)別在于動(dòng)態(tài)規(guī)劃需要在每一步作比較、取最優(yōu)值。對于數(shù)字三角形問題，我們可以這樣思考：設(shè)二維數(shù)組Aij，表示走到第i行的第j個(gè)數(shù)時(shí)所經(jīng) 過的數(shù)字和的最大值。例如對圖中三角形， A32=max1+6+2,1+3+2實(shí)現(xiàn)這樣，我們又可以得到遞推關(guān)系 Aij=pij+maxAi-1j-1,Ai-1j時(shí)注 意Ai-1j-1或Ai-1j不存在時(shí)的處理），其中pi

46、j表示第i行的第j個(gè)數(shù)的數(shù)值。此外，我們還需要一些初始值： pij （輸入）， A11=p11。最終我們可以求出A5j，結(jié)論自然是maxA5j 啦 分析這個(gè)算法，若層數(shù)大于5，則時(shí)間復(fù)雜度為0（n八2）。若用搜索，時(shí)間復(fù)雜度為0（2八n）。顯然動(dòng)態(tài)規(guī)劃效率高很多。為了更清楚地說明動(dòng)態(tài)規(guī)劃算法，我們先引入一些概念。階段 我們把問題劃分為幾步，在動(dòng)態(tài)規(guī)劃中，這叫做 “劃分階段 ”。數(shù)字三角 形中，每一層可看作是 個(gè)階段。狀態(tài) 每一階段有多種選擇，不同的選擇會(huì)有不同的結(jié)果，我們把每階段的不同 情形叫做 “狀態(tài)”。每一階段包括多個(gè)狀態(tài)。數(shù)字三角形中，表示走到第 j 個(gè)數(shù)時(shí)所經(jīng)過的數(shù)字和的最大值的動(dòng)態(tài)轉(zhuǎn)

47、移方程變量叫做狀態(tài)。我們可以用一個(gè)遞推式表示某階段到下一階段的遞推關(guān)系，這個(gè) 遞推式叫做動(dòng)態(tài)轉(zhuǎn)移方 程。動(dòng)態(tài)轉(zhuǎn)移方程一般含有 max 或 min 。決策 即對方法的選擇。每個(gè)階段都有一個(gè)決策。這樣的選擇是有范圍的，這個(gè) 范圍叫做 “ 決策允許集 合”。策略 一套完整的決策的組合。 “最優(yōu)策略 ”即最佳的決策組成的策略。還有一些概念因?yàn)槭褂幂^少，這里不再詳細(xì)介紹。注意可以運(yùn)用動(dòng)態(tài)規(guī)劃解決的問題的兩個(gè)必需特性： 最優(yōu)化原理 簡單地說，最優(yōu)策略某幾個(gè)連續(xù)階段上的決策組合，也是這幾個(gè)階 段組成的子問題的最優(yōu)策略。無后效性原則某階段以后的決策，與該階段之前的具體決策無關(guān)，只與該階段這正是動(dòng)這決定了的狀態(tài)

48、有關(guān)。注意，有些時(shí)候我們認(rèn)為不滿足這兩點(diǎn)的問題，換個(gè)角度看又是滿足的。態(tài)規(guī)劃的難點(diǎn)。接下 來我們就是要尋找合適的角度，找出滿足這兩個(gè)關(guān)系的算法。d. 石子合并：狀態(tài)的確定 用動(dòng)態(tài)規(guī)劃解決問題，首要也是最重要的步驟就是劃分階段、確定狀態(tài)。是否能成功運(yùn)用動(dòng)態(tài) 規(guī)劃方法。因此。確定一個(gè)可行的遞推思路是成功的關(guān)鍵。在這一過程中，要善于變通。石子合并： N 堆石子圍成一圈，每堆石子的量 ai 已知。每次可以將相鄰兩堆合并為 一堆，將合并后 石子的總量記為這次合并的得分。 N-1 次合并后石子成為一堆。 求這 N-1 次合并的得 分之和可能的最大 值。數(shù)據(jù)規(guī)模：N 100 , 算法構(gòu)造：分析數(shù)據(jù)規(guī)模算法可

49、承受的最大數(shù)據(jù)規(guī)模0（N八3），搜索必然超時(shí)，貪心可承 受數(shù)據(jù)規(guī)模太大，優(yōu)先 考慮動(dòng)態(tài)規(guī)劃。遞推思路一一計(jì)算將第i堆至第j堆完全合并所能獲得的最大得分。這是此題的關(guān)鍵?？紤]模擬每種合并 后的具體情形是行不通的。把問題變成這樣后就好解決了。劃分階段 以合并的次數(shù)作為標(biāo)準(zhǔn)劃分階段。 kvj n確定狀態(tài)一一第i堆至第j堆合并所能獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程 f(i,j)=maxf(i,k)+f(k+1,j),0i邊界狀態(tài) f(i,i)=ai分析知時(shí)間復(fù)雜度為0（n八3），滿足要求。遞推求出 f（1,n） 即可。動(dòng)態(tài)規(guī)劃特點(diǎn)是 “思路難，實(shí)現(xiàn)易 ”，這里不再給出源代碼。另外， N0IP2006 出現(xiàn)了一道石子合并的衍生問題。在Mars星球上，每個(gè)Mars人