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

1、2017-2018 NOIP中國(guó)計(jì)算機(jī)學(xué)會(huì)PAGE PAGE 702017-2018 NOIP 實(shí)用算法中國(guó)計(jì)算機(jī)學(xué)會(huì) 20171.模擬方法 3a.用數(shù)學(xué)量和圖形描述問(wèn)題 3b.模擬計(jì)算過(guò)程 3c.模擬時(shí)的優(yōu)化 3d.高精度計(jì)算算法 4習(xí)題 52.排序算法與算法時(shí)空復(fù)雜度 6a.簡(jiǎn)單排序算法 6b.快速排序、堆排序 6c.算法時(shí)空復(fù)雜度 7d.時(shí)空的簡(jiǎn)單優(yōu)化方法 8e.線性時(shí)間排序 8f.歸并排序 9g.合理選用排序算法 9習(xí)題 93.搜索 10a.復(fù)雜的模擬問(wèn)題與利用相似性 10b.函數(shù)的遞歸調(diào)用 10c.棧與深度優(yōu)先搜索 11d.深度優(yōu)先搜索的優(yōu)化 12e.隊(duì)列與廣度優(yōu)先搜索 12f.廣度

2、優(yōu)先搜索的優(yōu)化 12習(xí)題 134.貪心方法 14a.工程計(jì)劃模型 14b.部分背包與每步最優(yōu) 14c.構(gòu)造貪心算法 15習(xí)題 155.動(dòng)態(tài)規(guī)劃 16a.另一種形式的工程計(jì)劃 16b.記憶化搜索 16c.數(shù)字三角形：遞推地思考問(wèn)題 17d.石子合并：狀態(tài)的確定 17e.街道問(wèn)題：狀態(tài)量維數(shù)的確定與無(wú)后效性 18f.0-1 背包：巧妙地選取狀態(tài)量 19g.Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方式 20h.最長(zhǎng)非降子序列模型 20i.構(gòu)造動(dòng)態(tài)規(guī)劃算法 21j.動(dòng)態(tài)規(guī)劃、遞推、廣度優(yōu)先搜索的區(qū)別與轉(zhuǎn)化 21習(xí)題 216.常用數(shù)學(xué)方法 222a.排列組合 22b.遞推與通項(xiàng)的選用 237.分治 26a.

3、子問(wèn)題與母問(wèn)題的相似性 26b.二分查找 26c.分析算式 26d.最長(zhǎng)非降子序列的二分法 298.圖論思想 30a.圖論基礎(chǔ) 30b.圖的表示方法 30c.經(jīng)典圖論算法 30d.構(gòu)造圖論模型 32習(xí)題 33附件：關(guān)鍵路徑算法、篝火晚會(huì)問(wèn)題解法源文件3331.模擬方法a.用數(shù)學(xué)量和圖形描述問(wèn)題計(jì)算機(jī)處理的是數(shù)學(xué)量。若要用計(jì)算機(jī)解決實(shí)際問(wèn)題，需要把實(shí)際問(wèn)題抽象為數(shù)學(xué)量，或者數(shù)字。比如，記事本把文字按ASCII 碼表轉(zhuǎn)換為數(shù)字儲(chǔ)存起來(lái)，極品飛車把賽車的性能表示為數(shù)字，來(lái)權(quán)衡賽車的好壞。一個(gè)漂亮的算法，需要用數(shù)學(xué)量表示出來(lái)。任務(wù)：現(xiàn)有兩個(gè)軟件工程的制作任務(wù)，你的團(tuán)隊(duì)可以接手其中任意一個(gè)?，F(xiàn)要在兩個(gè)中

4、選擇一個(gè)，需要考慮制作成本，制作成功的可能性，可獲得經(jīng)濟(jì)收益的多少，對(duì)你的團(tuán)隊(duì)知名度的影響等等因素。你如何量化地分析和解決這個(gè)問(wèn)題？提示：需要把每一項(xiàng)都轉(zhuǎn)化為數(shù)值，必要時(shí)加入權(quán)值、計(jì)算期望。如果只考慮以上四個(gè)因素，可以得到以下數(shù)學(xué)式綜合收益=制作成功的概率*(可獲得經(jīng)濟(jì)收益-制作成本)*經(jīng)濟(jì)效益的權(quán)值+團(tuán)隊(duì)知名度的影響*社會(huì)效益的權(quán)值其中概率和兩個(gè)權(quán)值是需要估計(jì)的值。有時(shí)，我們需要用更直觀的圖形來(lái)描述實(shí)際問(wèn)題。圖論就是一個(gè)絕佳的方法。圖是一種表示離散量間關(guān)系的形式，它也是一種思想，常被用于建模。同時(shí)，前人也為我們提供了很多現(xiàn)成的圖論算法，能夠解決很多常見(jiàn)問(wèn)題，這些將在之后被提到。矩陣也是一種常

5、見(jiàn)的方法。有時(shí)矩陣被表示成三角形的形式，比如“楊輝三角”。矩陣常常和數(shù)學(xué)有關(guān)，在計(jì)算機(jī)計(jì)算時(shí)常常利用矩陣的遞推式。這也將在后面被提到。b.模擬計(jì)算過(guò)程模擬方法是最常見(jiàn)、最直接的算法構(gòu)建方法。任務(wù)：編程實(shí)現(xiàn)歐幾里得算法（輾轉(zhuǎn)相除法，求兩個(gè)數(shù)的最大公約數(shù)gcd(a,b)）提示：歐幾里得算法原理：gcd(a,b)=gcd(b,a mod b)歐幾里得算法的圖形描述| 168 63 | | 168 63 | 2| 42 |1.寫(xiě)下兩個(gè)數(shù)2.將兩數(shù)相除，余數(shù)寫(xiě)在較大的數(shù)下面| 168 63 | 2 | 168 63 | 21 | 42 21 | 1 | 42 21 | 2 整除3.將每列最下面的數(shù)相除，

6、余數(shù)寫(xiě)在被除數(shù)下面4.重復(fù)步驟3直至整除，此時(shí)最后寫(xiě)下的余數(shù)即為開(kāi)始時(shí)兩數(shù)的最大公約數(shù)這是一個(gè)簡(jiǎn)單的模擬算法，實(shí)際過(guò)程中，量間的關(guān)系往往比這復(fù)雜得多，因而，模擬算法可以是很復(fù)雜的。有些模擬算法還涉及到圖形和其他復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這需要我們熟練地運(yùn)用語(yǔ)言，巧妙地把其他關(guān)系轉(zhuǎn)化為數(shù)學(xué)量間關(guān)系。c.模擬時(shí)的優(yōu)化如果處理不當(dāng)，模擬方法寫(xiě)出的程序會(huì)非常長(zhǎng)。這要求我們?cè)谀M是將相似的步驟合為一體，適時(shí)利用函數(shù)簡(jiǎn)化程序。以上面的歐幾里得算法為例：4/*實(shí)現(xiàn)時(shí)，若將左邊一列數(shù)最下面的記為L(zhǎng)1000、右邊一列數(shù)記為R1000，顯然是不明智的，因?yàn)橹挥忻苛凶詈笠粋€(gè)數(shù)會(huì)在以后的計(jì)算中用到*/*實(shí)現(xiàn)方法一：及每一列最后

7、一個(gè)數(shù)分別為L(zhǎng)、R。輸入即可是L、R，返回gcd(L,R)*/int Euclid_1(int L,int R)for(;)L=L%R;if(L=0)return R;R=R%L;if(R=0)return L;/*我們發(fā)現(xiàn)有兩步是相似的。因而我們可以把它簡(jiǎn)化為實(shí)現(xiàn)方法二*/int Euclid_2(int L,int R)int t;for(;)t=R; R=L%R; L=t;if(R=0)return L;/*甚至我們可以寫(xiě)成遞歸形式。以下是實(shí)現(xiàn)方法三*/int Euclid_3(int L,int R)if(L%R=0)return R;else return Euclid_3(R,L%

8、R);這個(gè)實(shí)例主要體現(xiàn)模擬算法的簡(jiǎn)化過(guò)程。雖然在這樣小的程序段中，這樣的簡(jiǎn)化作用不大，但遇到復(fù)雜的模擬問(wèn)題，這種利用相似性的簡(jiǎn)化便非常有用了。應(yīng)當(dāng)重視這樣的代碼優(yōu)化。d.高精度計(jì)算算法競(jìng)賽中經(jīng)常會(huì)用上一些很大的數(shù)，超出長(zhǎng)整型的數(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

9、n-1。簡(jiǎn)單地說(shuō)，若把H 定為unsigned 型，高精度數(shù)每一位上最大數(shù)最好為9999。這樣既能盡量利用儲(chǔ)存空間，又便于輸出。另外，高精度數(shù)有時(shí)會(huì)用到負(fù)數(shù)。在補(bǔ)碼的體系中，仍然可以按正數(shù)的方法處理負(fù)數(shù)，但是要特別注意輸出時(shí)的問(wèn)題，和對(duì)溢出的防止。任務(wù)：實(shí)現(xiàn)高精度運(yùn)算加法提示：設(shè)計(jì)函數(shù)unsigned *HAdd(unsigned N1,unsigned N2,unsigned Ans)，從末位起相加，注意是否進(jìn)位。顯然，減法作為加法的逆運(yùn)算，也很容易實(shí)現(xiàn)。另一種聰明的辦法是，對(duì)減數(shù)每一位取補(bǔ)碼，在做加法5即可。請(qǐng)讀者自行實(shí)現(xiàn)高精度減法。高精度乘法困難一些。我推薦的方法是，先考慮多位高精度數(shù)乘

10、一位高精度數(shù)的過(guò)程。多位高精度數(shù)乘多位高精度數(shù)可以轉(zhuǎn)化為多位高精度數(shù)乘另一高精度數(shù)每一位，再將結(jié)果相加的過(guò)程。下面給出多位高精度數(shù)乘一位高精度數(shù)的源代碼：#define H_Bit 256 /*定義常數(shù)：高精度數(shù)位數(shù)*/unsigned *HTimesInt(unsigned N1,int N2,unsigned Ans) /*N1為多位高精度數(shù)，N2為高精度數(shù)的一位，Ans為另一高精度數(shù)，用于儲(chǔ)存結(jié)果*/*這里允許N1與Ans 相同*/unsigned i,up=0;unsigned long temp;for(i=H_Bit-1;i=H_Bit;i-)temp=N1i*N2+up;up=t

11、emp/10000;Ansi=(unsigned)(temp%10000);return Ans;/*函數(shù)返回作為答案的高精度數(shù)首地址，這樣更便于高精度運(yùn)算函數(shù)的使用，例如連乘可以寫(xiě)成HTimesInt(HTimesInt(N1,N2,Ans),N3,Ans)*/高精度數(shù)的輸入輸出需要專門的函數(shù)。針對(duì)不同語(yǔ)言的不同特點(diǎn)，可以比較容易地寫(xiě)出這兩個(gè)函數(shù)。但要注意輸出非首位數(shù)位上的“0”。習(xí)題模擬方法的習(xí)題感謝深藍(lán)評(píng)測(cè)系統(tǒng)提供習(xí)題62.排序算法與算法時(shí)空復(fù)雜度a.簡(jiǎn)單排序算法簡(jiǎn)單排序算法包括冒泡排序、插入排序、選擇排序。這三種算法容易理解、編寫(xiě)方便，適用于數(shù)據(jù)規(guī)模較小的情形。冒泡排序（Bubble

12、Sort）的基本思路是：（以從小到大排序?yàn)槔那暗胶笾饌€(gè)比較相鄰兩數(shù)，若前數(shù)大于后數(shù)，就將兩數(shù)交換。不斷重復(fù)這一過(guò)程，直至全部數(shù)字已按從小到大排好?？紤]到實(shí)用性的問(wèn)題，插入排序和選擇排序這里不再介紹。對(duì)于NOIP 提高組而言，這些算法時(shí)間復(fù)雜度過(guò)高，很難應(yīng)付較大的數(shù)據(jù)規(guī)模。建議盡量不要采用簡(jiǎn)單排序算法，除非你十分確信數(shù)據(jù)規(guī)模在可承受范圍之內(nèi)。b.快速排序、堆排序快速排序和堆排序是比簡(jiǎn)單排序快的排序算法，在競(jìng)賽中常常被采用。這里，我們介紹快速排序算法。堆排序的實(shí)現(xiàn)不作介紹，若想了解，可咨詢谷歌或百度?？焖倥判颍≦uick Sort）基于分治思想。它的基本思路是：（以從小到大排序?yàn)槔┤∫粋€(gè)數(shù)作

13、為標(biāo)記元素，將比它大的數(shù)放在它右側(cè)，比它小的數(shù)放在它左側(cè)，再通過(guò)遞歸的方法，將左側(cè)的數(shù)用以上的方法排好，右側(cè)的數(shù)也用以上的方法排好即可。下面這個(gè)視頻能很直觀地比較冒泡排序（Bubble Sort）和快速排序（Quick Sort）：在數(shù)據(jù)規(guī)模很大時(shí)，平均情況下快排比冒泡快很多。在處理NOIP 提高組含排序的問(wèn)題時(shí)，一般要選擇快速排序或堆排序。下面將介紹快速排序的實(shí)現(xiàn)（以從小到大排序?yàn)槔?。快排運(yùn)用分治思想，因而要用函數(shù)的遞歸調(diào)用來(lái)實(shí)現(xiàn)：void QuickSort(int a,int st,int stp) /這里也可以定義成void QuickSort(int*st,int len)。為了便

14、于理解，我使用前一種寫(xiě)法。int mid;mid=partition(a,st,stp); /partition()用于確定標(biāo)記元素的位置。if(lmid-1)QuickSort(a,st,mid-1);if(mid+1r)QuickSort(a,mid+1,stp);現(xiàn)在的關(guān)鍵問(wèn)題在于如何寫(xiě)partition()。寫(xiě)法一：對(duì)于數(shù)列5 6 7 5 3 8 1 6 21.取首個(gè)元素做標(biāo)記元素，取出它，令指針p 指向最右邊的數(shù)的右邊_6 7 5 3 8 1 6 2 p-2.將p 向左移動(dòng)到小于標(biāo)記元素的數(shù)（或空缺處）為止。若指向空缺，則跳到5；否則將該數(shù)和p 移到空缺處 p-2 6 7 5 3 8

15、 1 6 _3.將p 向右移動(dòng)到大于標(biāo)記元素的數(shù)（或空缺處）為止。若指向空缺，則跳到5；否則將該數(shù)和p 移到空缺處 2 _ 7 5 3 8 1 6 p-64.重復(fù)2和3。2 p-1 7 5 3 8 _ 6 62 1 _ 5 3 8 p-7 6 672 1 p-3 5 _ 8 7 6 65.把標(biāo)記元素放入空格處 2 1 3 5 p-5 8 7 6 6寫(xiě)法二：寫(xiě)法二比寫(xiě)法一短一些，但理論上講，寫(xiě)法二要慢一些（因?yàn)樗髻x值運(yùn)算多一些）。下面給出源代碼與分析：void QuickSort(long a,long st,long stp) /這里將partition()結(jié)合進(jìn)QuickSort()中l(wèi)o

16、ng t,n,l,r;n=ast;l=st+1;r=stp;for(;)for(;al=n & l=n & rst;r-); /從左找，找到一個(gè)大于標(biāo)記元素的數(shù)if(l=r)break; /如果l 在r 右側(cè)，則跳出t=al;al=ar;ar=t; /交換，使小于標(biāo)記元素的在左，大于標(biāo)記元素的在右ast=ar; /取出最右側(cè)的小于標(biāo)記元素的數(shù)寫(xiě)入空缺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ì)很低。為了解決排列整齊的情形，我們可以使用

17、隨機(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()表示。通常表示時(shí)間復(fù)雜度時(shí)，我們只保留影響最大的項(xiàng)，并忽略該項(xiàng)的系數(shù)。例如主要運(yùn)算為賦值的算法，賦值做了3n3+n2+8次，則認(rèn)為它的復(fù)雜度為O(n3)；若主要運(yùn)算為比較，比較做了4*2n+2*n4+700次，由于數(shù)據(jù)很大時(shí)，指數(shù)級(jí)增長(zhǎng)的2n 影響最大，我們認(rèn)為它的時(shí)間復(fù)雜度為O(2n)。常見(jiàn)的時(shí)間復(fù)雜度有下列幾個(gè)：O(n) 貪心算法多數(shù)情況下為此時(shí)間復(fù)雜度O(nlbn) 有時(shí)帶有分治思想

18、的算法的時(shí)間復(fù)雜度（注lbn 表示以2為底的n 的對(duì)數(shù)）O(n2) 有時(shí)動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度O(n3) 有時(shí)動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度O(2n) 有時(shí)搜索算法的時(shí)間復(fù)雜度O(n!) 有時(shí)搜索算法的時(shí)間復(fù)雜度有時(shí)時(shí)間復(fù)雜度中含有兩個(gè)或多個(gè)字母，比如遍歷一個(gè)m*n 的矩陣，時(shí)間復(fù)雜度為O(m*n)。要注意的是，時(shí)間復(fù)雜度相同的兩個(gè)算法，它的實(shí)際執(zhí)行時(shí)間可能會(huì)有數(shù)倍的差距，因而實(shí)現(xiàn)時(shí)要特別注意細(xì)節(jié)處的優(yōu)化。8NOIP 提高組執(zhí)行時(shí)限常常為1s。一般認(rèn)為，將數(shù)據(jù)規(guī)模代入到時(shí)間復(fù)雜度，若所得值小于或接近于1000000，就是絕對(duì)安全的、不超時(shí)的。例如，O(n2)的動(dòng)態(tài)規(guī)劃算法，可承受的數(shù)據(jù)規(guī)模是n1000；O

19、(2n)的搜索算法，可承受的數(shù)據(jù)規(guī)模是n20；O(n!)的搜索算法，可承受的數(shù)據(jù)規(guī)模是n9。實(shí)際上，以現(xiàn)在的CPU 運(yùn)行速度，5000000也應(yīng)該不成問(wèn)題?？臻g復(fù)雜度：一個(gè)算法消耗儲(chǔ)存空間（內(nèi)存）的大小，用O()表示?？臻g復(fù)雜度的表示規(guī)則與時(shí)間復(fù)雜度類似。在實(shí)際應(yīng)用時(shí)，空間的占用是需要特別注意的問(wèn)題。太大的數(shù)組經(jīng)常是開(kāi)不出來(lái)的，即使開(kāi)出來(lái)了，遍歷的時(shí)間消耗也是驚人的。下面我們簡(jiǎn)單地分析一下簡(jiǎn)單排序算法、快速排序、堆排序的時(shí)空復(fù)雜度。這三種算法都是基于比較的排序算法，以比較次數(shù)作為主要運(yùn)算。簡(jiǎn)單排序算法最差時(shí)需做n2次比較，平均情況下時(shí)間復(fù)雜度通常被認(rèn)為是O(n2)?？焖倥判蜃畈顣r(shí)需做n2次比較

20、，可以證明平均情況下需做nlbn 次比較，時(shí)間復(fù)雜度是O(nlbn)。堆排序時(shí)間復(fù)雜度是O(nlbn)?？臻g上，三者都不需要額外開(kāi)辟暫存數(shù)組，快排遞歸調(diào)用時(shí)需要使用稍多一些的儲(chǔ)存空間。綜合來(lái)看，快速排序、堆排序優(yōu)于簡(jiǎn)單排序算法。另外，可以證明基于比較的排序算法時(shí)間復(fù)雜度下界為O(nlbn)。d.時(shí)空的簡(jiǎn)單優(yōu)化方法時(shí)間上的優(yōu)化在于少做運(yùn)算、做耗時(shí)短的運(yùn)算等。有幾個(gè)規(guī)律需要注意：整型運(yùn)算耗時(shí)遠(yuǎn)低于實(shí)型運(yùn)算耗時(shí)。+、- 運(yùn)算非?？欤p法是將減數(shù)取補(bǔ)碼后與被減數(shù)相加，其中位運(yùn)算更快一些，但是減法也比加法稍慢些。）* 運(yùn)算比加法慢得多/ 運(yùn)算比乘法慢得多比較運(yùn)算慢于四則運(yùn)算賦值運(yùn)算慢于比較運(yùn)算（因?yàn)橐獙?xiě)

21、內(nèi)存）這些規(guī)律我們可以從宏觀上把握。事實(shí)上，究竟做了幾步運(yùn)算、幾次賦值、變量在內(nèi)存還是緩存等多數(shù)由編譯器、系統(tǒng)決定。但是，少做運(yùn)算（尤其在循環(huán)體、遞歸體中）一定能很大程度節(jié)省時(shí)間。下面來(lái)舉一個(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)(n-m+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)為止。我覺(jué)得這種只用加法的運(yùn)算會(huì)快

22、些，盡管加法多一些。（我沒(méi)試驗(yàn)過(guò)，你可以去試一下。）空間上的優(yōu)化主要在于減小數(shù)組大小、降低數(shù)組維數(shù)等。常用的節(jié)省內(nèi)存的方法有：壓縮儲(chǔ)存例：數(shù)組中每個(gè)數(shù)都只有0、1兩種可能，則可以按位儲(chǔ)存，空間壓縮為原來(lái)的八分之一。覆蓋舊數(shù)據(jù)例：矩陣中每一行的值只與上一行有關(guān)，輸出只和最末行有關(guān)，則可將奇數(shù)行儲(chǔ)存在第一行，偶數(shù)行儲(chǔ)存在第二行，降低空間復(fù)雜度。要注意的是，對(duì)空間的優(yōu)化即使不改變復(fù)雜度、只是改變n 的系數(shù)也是極有意義的?？臻g復(fù)雜度有時(shí)對(duì)時(shí)間也有影響，要想方設(shè)法進(jìn)行優(yōu)化。e.線性時(shí)間排序基于比較的排序算法時(shí)間復(fù)雜度下界為O(nlbn)。因而，若還要降低復(fù)雜度，要放棄基于比較的排序9算法。有一類排序算法

23、叫做線性時(shí)間排序，它們的時(shí)間復(fù)雜度為O(n)。下面介紹一種。計(jì)數(shù)排序思路：開(kāi)辟暫存數(shù)組b，bk表示欲排序數(shù)組a中k 出現(xiàn)的次數(shù)（需要遍歷a），最后遍歷b，可將a排好。這種想法非常簡(jiǎn)單，實(shí)現(xiàn)也很容易。事實(shí)證明，在a取值范圍很小（如整型范圍）時(shí)，它是很高效的排序算法，比快排快不少。可是a取值范圍較大（如長(zhǎng)整型范圍）時(shí)，它的執(zhí)行時(shí)間會(huì)變長(zhǎng)，而且數(shù)組b有時(shí)開(kāi)不出來(lái)。實(shí)際上計(jì)數(shù)排序時(shí)間復(fù)雜度為O(n+m)，空間復(fù)雜度也為O(n+m)，m 表示a取值范圍。若m 很大，則也不能在時(shí)限內(nèi)執(zhí)行完。f.歸并排序有一種排序時(shí)極為常見(jiàn)的情形：有一張成績(jī)表，記錄著許多學(xué)生的成績(jī)，要將他們按成績(jī)排序，但成績(jī)相同者的相對(duì)順

24、序不能改變。換句話說(shuō)，ABCDE 五人，A、C、D 成績(jī)相同，顯然排序完之后會(huì)排在一起，現(xiàn)在的要求是：他們排在一起的順序也必須是ACD，不能是ADC、CAD這樣的實(shí)際問(wèn)題涉及到排序的穩(wěn)定性。排序的穩(wěn)定性：一個(gè)排序算法，若可使排序前后關(guān)鍵字相同的項(xiàng)相對(duì)順序不變，則稱該排序算法是穩(wěn)定的排序算法。下面我們來(lái)考察常見(jiàn)排序算法的穩(wěn)定性。在編寫(xiě)合理的情況下，簡(jiǎn)單排序算法是穩(wěn)定的；快速排序、堆排序是不穩(wěn)定的（你可以好好想想這是為什么）。在NOIP 中，往往排序是沒(méi)有附帶其他項(xiàng)目的，也就不要求排序穩(wěn)定?？焖倥判颉⒍雅判蛉匀皇亲罴堰x擇。可是有沒(méi)有時(shí)間復(fù)雜度為O(nlbn)的穩(wěn)定的排序算法呢？有的。歸并排序基于分

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

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

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

28、體地，在每一位的選取時(shí)，都從a 開(kāi)始，到后面位的字母組合全部嘗試過(guò)，再跳到下一個(gè)字母；若（非首位）已經(jīng)跳到z 而還需再跳一個(gè)字母時(shí)，就跳到a，同時(shí)讓它的前一位跳到下一個(gè)字母。例如，n=3時(shí)，形成的字母組合的順序是a a a - aaab - aabc - aac.z - aazb a - abab - abb.z - abzc a - acaz z - azzb a a - baaz z - bzzc a a - caaz z z - zzz以上描述的是一種常見(jiàn)的遍歷方法。我們注意到，選定每一位的過(guò)程是極其相似的。我們需要利用這種相似性。b.函數(shù)的遞歸調(diào)用結(jié)構(gòu)化編程語(yǔ)言提供的最大好處無(wú)疑是函數(shù)

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

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

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

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

33、標(biāo)節(jié)點(diǎn)一起開(kāi)始搜索。由于NOIP 提高組近年來(lái)幾乎不出搜索題；可用搜索的題目，由于搜索時(shí)間復(fù)雜度太高，數(shù)據(jù)規(guī)模太大，搜索只能得部分分?jǐn)?shù)。加之搜索思路較簡(jiǎn)單，搜索法這里不再詳細(xì)敘述。若想了解，大家可以用搜索引擎搜索。習(xí)題搜索的習(xí)題感謝深藍(lán)評(píng)測(cè)系統(tǒng)提供習(xí)題144.貪心方法a.工程計(jì)劃模型我們常常碰到這樣的問(wèn)題：完成一個(gè)工程需要若干個(gè)步驟，每個(gè)步驟都有若干種方法，圖示步驟a 步驟b 步驟c . 步驟n方法b1 方法c1方法a1 方法b2 方法c2 方法n1方法a2 方法b3 方法c3方法c4每個(gè)方法有一個(gè)權(quán)值（如效率、質(zhì)量），其大小往往和其他步驟中選取的方法有關(guān)。有些時(shí)候權(quán)值無(wú)意義，表示方法不可選擇

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

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

36、們先裝入單位重量?jī)r(jià)值最高的物品，再裝入第二高的直到重量達(dá)到M（有必要時(shí)最后一件物品只裝一部分），已達(dá)到物品總價(jià)值最高。這個(gè)證明應(yīng)該很嚴(yán)謹(jǐn)吧該算法時(shí)間復(fù)雜度O(n)，效率很高；而且實(shí)現(xiàn)很容易。這些是貪心法最大的特點(diǎn)。很多競(jìng)賽題看似可以用貪心法，其實(shí)貪心法得不到最優(yōu)解，原因是每一步的選擇對(duì)其他步驟有影響。數(shù)字三角形問(wèn)題：有一個(gè)數(shù)字三角形（如下圖）?，F(xiàn)有一只螞蟻從頂層開(kāi)始向下走，每走下一級(jí)時(shí)，可向左下方向或右下方向走。求走到底層后它所經(jīng)過(guò)的數(shù)的最大值。16 38 2 62 1 6 53 2 4 7 6如果用貪心法，每次向最大的方向走，得到結(jié)果為1+6+8+2+3=20?？墒敲髅鬟€有另一條路，1+3+

37、6+6+7=23。15問(wèn)題出在哪？每次的選擇對(duì)后面的步驟會(huì)有影響！第三級(jí)選了8，就選不到第四、五級(jí)較大的數(shù)了。這個(gè)問(wèn)題正確的解法會(huì)在下一章介紹。有一個(gè)很實(shí)用的小技巧：競(jìng)賽題會(huì)給出數(shù)據(jù)規(guī)模。通過(guò)數(shù)據(jù)規(guī)模，我們可以大致判斷該用何種算法。貪心算法可承受的數(shù)據(jù)規(guī)模很大，一般都會(huì)上萬(wàn)。如果給出的數(shù)據(jù)規(guī)模是100或1000，優(yōu)先考慮動(dòng)態(tài)規(guī)劃吧。c.構(gòu)造貪心算法構(gòu)造與證明是貪心算法的難點(diǎn)，常常要求我們要有敏銳的觀察力、多角度思考的變通能力、豐富的數(shù)學(xué)知識(shí)和推理能力。下面舉幾個(gè)貪心算法的例子，供大家揣摩、掌握規(guī)律。刪數(shù)問(wèn)題：給出一個(gè)N 位的十進(jìn)制高精度數(shù)，要求從中刪掉S 個(gè)數(shù)字（其余數(shù)字相對(duì)位置不得改變），使

38、剩余數(shù)字組成的數(shù)最小。算法構(gòu)造：1.每次找出最靠前的這樣的一對(duì)數(shù)字兩個(gè)數(shù)字緊鄰，且前面的數(shù)字大于后面的。刪除這對(duì)數(shù)字中靠前的一個(gè)。2.重復(fù)步驟1，直至刪去了S 個(gè)數(shù)字或找不到這樣的一對(duì)數(shù)。3.若還未刪夠S 個(gè)數(shù)字，則舍棄末尾的部分?jǐn)?shù)字，取前N-S 個(gè)。證明思路：顯然，在只刪一個(gè)數(shù)字時(shí)，唯有步驟1的方法能使數(shù)變小；可推理得出，刪多個(gè)數(shù)字時(shí)，所有最優(yōu)的方法都可看做是對(duì)步驟1的重復(fù)。也就是說(shuō)，以上方法是最優(yōu)策略之一。在文末的附件中給出了這個(gè)算法的源代碼。工序問(wèn)題：n 件物品，每件需依次在A、B 機(jī)床上加工。已知第i 件在A、B 所需加工時(shí)間分別為Ai、Bi，設(shè)計(jì)一加工順序，使所需加工總時(shí)間最短。算法

39、構(gòu)造：1.設(shè)置集合F、M、S：先加工F 中的，再加工M 中的，最后加工S 中的。2.對(duì)第i 件，若AiBi，則歸入S；若Ai=Bi，則歸入M。3.對(duì)F 中的元素按Ai升序排列，S 中的按Bi降序排列。證明思路：1.F 中的能“拉開(kāi)”A、B 加工同一件工件的結(jié)束時(shí)刻，為后面的工件加工“拉開(kāi)時(shí)間差”，利于節(jié)省總時(shí)間。S 中的剛好相反。因而，F(xiàn) 中元素放在最前一定是最優(yōu)策略之一。2.F 中Ai小的前置，可以縮短開(kāi)始時(shí)B 的空閑時(shí)間，但會(huì)使F 所有工件“拉開(kāi)的時(shí)間差”縮短。不過(guò)可以證明，后者帶來(lái)的損失不大于前者獲得的優(yōu)勢(shì)。對(duì)稱地，對(duì)S 也一樣。因而步驟3是可行的。種樹(shù)問(wèn)題：一條街道分為n 個(gè)區(qū)域（按1

40、-n 編號(hào)），每個(gè)都可種一棵樹(shù)。有m 戶居民，每戶會(huì)要求在區(qū)域i-j 區(qū)間內(nèi)種至少一棵樹(shù)?，F(xiàn)求一個(gè)能滿足所有要求且種樹(shù)最少的方案。算法構(gòu)造：1.對(duì)于要求，以區(qū)間右端（升序）為首要關(guān)鍵字，左端（升序）為次要關(guān)鍵字排序。2.按排好的序依次考察這些要求，若未滿足，則在其最右端的區(qū)域種樹(shù)，這時(shí)可能會(huì)滿足多個(gè)要求。證明思路：解法并不唯一，關(guān)鍵是證明沒(méi)有比該解法更好的解法。按步驟1排序之后，會(huì)發(fā)現(xiàn)對(duì)于每個(gè)要求，在最右邊的區(qū)域內(nèi)種樹(shù)所得的結(jié)果總不會(huì)差于在其他區(qū)域種樹(shù)。至于為什么這樣排序，留給你讀者們思考吧。在文末的附件中給出了這個(gè)算法的源代碼。習(xí)題貪心方法的習(xí)題感謝深藍(lán)評(píng)測(cè)系統(tǒng)提供習(xí)題165.動(dòng)態(tài)規(guī)劃a.另

41、一種形式的工程計(jì)劃b.記憶化搜索c.數(shù)字三角形：遞推地思考問(wèn)題d.石子合并：狀態(tài)的確定e.街道問(wèn)題：狀態(tài)量維數(shù)的確定與無(wú)后效性f.0-1背包：巧妙地選取狀態(tài)量g.Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方式h.最長(zhǎng)非降子序列模型i.構(gòu)造動(dòng)態(tài)規(guī)劃算法j.動(dòng)態(tài)規(guī)劃、遞推、廣度優(yōu)先搜索的區(qū)別與轉(zhuǎn)化a.另一種形式的工程計(jì)劃上一章我們講過(guò)，若工程計(jì)劃問(wèn)題中某一步權(quán)值只和上一步或少數(shù)幾步的選擇有關(guān)，我們可以使用效率較高的動(dòng)態(tài)規(guī)劃算法?？聪旅孢@個(gè)問(wèn)題：4-9/ 1-2-5-3-1 / /1-7-8上圖的數(shù)字間連了線。現(xiàn)要從最左邊的“1”走到最右邊的“1”，每次都只能沿線向右走到右邊一列的某個(gè)數(shù)上，要求找出一條路

42、徑，路徑上的五個(gè)數(shù)之和最大。當(dāng)然我們可以把這理解為工程計(jì)劃問(wèn)題的一種形式。這里，每一步的選擇與上一步相關(guān)；似乎也與前面幾步的選擇有關(guān)，但是注意，前幾步的影響都可以表現(xiàn)在上一步上，上一步方法的選擇已經(jīng)可以獨(dú)立決定這一步每種選擇的權(quán)值。此處適用動(dòng)態(tài)規(guī)劃。換句“專業(yè)”點(diǎn)的話，這里滿足“無(wú)后效性原則”，即之后過(guò)程不受之前具體過(guò)程的影響。這在后面會(huì)具體說(shuō)明。b.記憶化搜索再講動(dòng)態(tài)規(guī)劃之前，我們先接觸一下記憶化搜索。注意到，在深度優(yōu)先搜索中，用于遞歸的函數(shù)cal()有時(shí)會(huì)被用同樣的參數(shù)調(diào)用多次。你可能很容易想到，如果在第一次調(diào)用時(shí)把參數(shù)和對(duì)應(yīng)的函數(shù)值儲(chǔ)存起來(lái)，若以后再以同樣的參數(shù)調(diào)用，就不用執(zhí)行遞歸函數(shù)，

43、直接取出所得的值，不是快得多？如果你能想到這些，你就已經(jīng)學(xué)會(huì)記憶化搜索了。事實(shí)上，記憶化搜索能大幅提高效率的地方，往往是在動(dòng)態(tài)規(guī)劃的題目中。動(dòng)態(tài)規(guī)劃能解決的問(wèn)題，往往可以用記憶化搜索替代動(dòng)態(tài)規(guī)劃解決。如果你實(shí)在無(wú)法掌握動(dòng)態(tài)規(guī)劃，你可以選擇使用記憶化搜索。不過(guò)你要注意以下事實(shí)：動(dòng)態(tài)規(guī)劃程序?qū)崿F(xiàn)較容易，程序段短，便于調(diào)試；記憶化搜索實(shí)現(xiàn)就比較繁瑣。雖然記憶化搜索可以把時(shí)間復(fù)雜度降低到動(dòng)態(tài)規(guī)劃的水平，但是實(shí)際執(zhí)行時(shí)間會(huì)大于動(dòng)態(tài)規(guī)劃，甚至有幾倍到十幾倍的差距。這里不給出記憶化搜索的代碼了。我們還是首選動(dòng)態(tài)規(guī)劃吧17c.數(shù)字三角形：遞推地思考問(wèn)題上一章中我們講過(guò)數(shù)字三角形問(wèn)題：有一個(gè)數(shù)字三角形（如下圖）

44、?，F(xiàn)有一只螞蟻從頂層開(kāi)始向下走，每走下一級(jí)時(shí)，可向左下方向或右下方向走。求走到底層后它所經(jīng)過(guò)的數(shù)的最大值。16 38 2 62 1 6 53 2 4 7 6對(duì)于這個(gè)問(wèn)題，貪心法得不到最優(yōu)解，搜索法效率太低。我們知道，深度優(yōu)先搜索利用了遞歸式的思維，動(dòng)態(tài)規(guī)劃中，我們使用遞推式的思維。遞歸：要知道第五層時(shí)的最大值，就要知道第四層時(shí)的最大值；要知道第四層時(shí)的最大值，就要知道第三層時(shí)的最大值而每一步推導(dǎo)的方法是相似的。遞推：知道第一層的最大值，就能知道第二層的最大值，也就能知道第三層的最大值而每一步推導(dǎo)的方法是相似的。對(duì)比之下，遞推思維不是從結(jié)論入手的，有時(shí)容易失去方向；但是有時(shí)卻可以有很高的效率。動(dòng)

45、態(tài)規(guī)劃和普通遞推的區(qū)別在于動(dòng)態(tài)規(guī)劃需要在每一步作比較、取最優(yōu)值。對(duì)于數(shù)字三角形問(wèn)題，我們可以這樣思考：設(shè)二維數(shù)組Aij，表示走到第i 行的第j 個(gè)數(shù)時(shí)所經(jīng)過(guò)的數(shù)字和的最大值。例如對(duì)圖中三角形，A32=max1+6+2,1+3+2。這樣，我們又可以得到遞推關(guān)系A(chǔ)ij=pij+maxAi-1j-1,Ai-1j（實(shí)現(xiàn)時(shí)注意Ai-1j- 1或Ai-1j不存在時(shí)的處理），其中pij表示第i 行的第j 個(gè)數(shù)的數(shù)值。此外，我們還需要一些初始值：pij（輸入），A11=p11。最終我們可以求出A5j，結(jié)論自然是maxA5j啦分析這個(gè)算法，若層數(shù)大于5，則時(shí)間復(fù)雜度為O(n2)。若用搜索，時(shí)間復(fù)雜度為O(2n)

46、。顯然動(dòng)態(tài)規(guī)劃效率高很多。為了更清楚地說(shuō)明動(dòng)態(tài)規(guī)劃算法，我們先引入一些概念。階段我們把問(wèn)題劃分為幾步，在動(dòng)態(tài)規(guī)劃中，這叫做“劃分階段”。數(shù)字三角形中，每一層可看作是一個(gè)階段。狀態(tài)每一階段有多種選擇，不同的選擇會(huì)有不同的結(jié)果，我們把每階段的不同情形叫做“狀態(tài)”。每一階段包括多個(gè)狀態(tài)。數(shù)字三角形中，表示走到第j 個(gè)數(shù)時(shí)所經(jīng)過(guò)的數(shù)字和的最大值的變量叫做狀態(tài)。動(dòng)態(tài)轉(zhuǎn)移方程我們可以用一個(gè)遞推式表示某階段到下一階段的遞推關(guān)系，這個(gè)遞推式叫做動(dòng)態(tài)轉(zhuǎn)移方程。動(dòng)態(tài)轉(zhuǎn)移方程一般含有max或min。決策即對(duì)方法的選擇。每個(gè)階段都有一個(gè)決策。這樣的選擇是有范圍的，這個(gè)范圍叫做“決策允許集合”。策略一套完整的決策的組合

47、?！白顑?yōu)策略”即最佳的決策組成的策略。還有一些概念因?yàn)槭褂幂^少，這里不再詳細(xì)介紹。注意可以運(yùn)用動(dòng)態(tài)規(guī)劃解決的問(wèn)題的兩個(gè)必需特性：最優(yōu)化原理簡(jiǎn)單地說(shuō)，最優(yōu)策略某幾個(gè)連續(xù)階段上的決策組合，也是這幾個(gè)階段組成的子問(wèn)題的最優(yōu)策略。無(wú)后效性原則某階段以后的決策，與該階段之前的具體決策無(wú)關(guān)，只與該階段的狀態(tài)有關(guān)。注意，有些時(shí)候我們認(rèn)為不滿足這兩點(diǎn)的問(wèn)題，換個(gè)角度看又是滿足的。這正是動(dòng)態(tài)規(guī)劃的難點(diǎn)。接下來(lái)我們就是要尋找合適的角度，找出滿足這兩個(gè)關(guān)系的算法。d.石子合并：狀態(tài)的確定用動(dòng)態(tài)規(guī)劃解決問(wèn)題，首要也是最重要的步驟就是劃分階段、確定狀態(tài)。這決定了是否能成功運(yùn)用動(dòng)態(tài)規(guī)劃方法。因此。確定一個(gè)可行的遞推思路是

48、成功的關(guān)鍵。18在這一過(guò)程中，要善于變通。石子合并：N 堆石子圍成一圈，每堆石子的量ai已知。每次可以將相鄰兩堆合并為一堆，將合并后石子的總量記為這次合并的得分。N-1次合并后石子成為一堆。求這N-1次合并的得分之和可能的最大值。數(shù)據(jù)規(guī)模：N100，ai20000000算法構(gòu)造：分析數(shù)據(jù)規(guī)模算法可承受的最大數(shù)據(jù)規(guī)模O(N3)，搜索必然超時(shí)，貪心可承受數(shù)據(jù)規(guī)模太大，優(yōu)先考慮動(dòng)態(tài)規(guī)劃。遞推思路計(jì)算將第i 堆至第j 堆完全合并所能獲得的最大得分。這是此題的關(guān)鍵?？紤]模擬每種合并后的具體情形是行不通的。把問(wèn)題變成這樣后就好解決了。劃分階段以合并的次數(shù)作為標(biāo)準(zhǔn)劃分階段。確定狀態(tài)第i 堆至第j 堆合并所能

49、獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程f(i,j)=maxf(i,k)+f(k+1,j),0ikjn邊界狀態(tài)f(i,i)=ai分析知時(shí)間復(fù)雜度為O(n3)，滿足要求。遞推求出f(1,n)即可。動(dòng)態(tài)規(guī)劃特點(diǎn)是“思路難，實(shí)現(xiàn)易”，這里不再給出源代碼。另外，NOIP2006出現(xiàn)了一道石子合并的衍生問(wèn)題。在Mars 星球上，每個(gè)Mars 人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N 顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤（吸盤是Mars 人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一

50、顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。需要時(shí)，Mars 人就用吸盤夾住相鄰的兩顆珠子，通過(guò)聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。建議讀者自己思考解決，以熟悉動(dòng)態(tài)規(guī)劃的思維過(guò)程。在附件中給出解法的源代碼。e.街道問(wèn)題：狀態(tài)量維數(shù)的確定與無(wú)后效性下面是動(dòng)態(tài)規(guī)劃的經(jīng)典問(wèn)題之一：街道問(wèn)題。下圖表示一個(gè)街道?，F(xiàn)有類似這樣的N*N 的街道，且每段路有一

51、個(gè)權(quán)值。現(xiàn)在要從左上角沿線走到右下角，每次只能向右或向下走。求經(jīng)過(guò)路段權(quán)值和的最大值。數(shù)據(jù)規(guī)模：N10003 2 5 64 3 7 2 87-5-1-6-2 3 6 8 23-1-2-9-6 8 5 1 44-5-9-8-9 3 2 8 16-4-4-2-分析數(shù)據(jù)規(guī)模算法可承受的最大數(shù)據(jù)規(guī)模O(N2)，搜索必然超時(shí)，貪心可承受數(shù)據(jù)規(guī)模太大，優(yōu)先考慮動(dòng)態(tài)規(guī)劃。遞推思路從左上角向右下角推，求出走到每一點(diǎn)所經(jīng)過(guò)權(quán)值和的最大值。劃分階段按斜向()劃分19剩下的讀者自己思考。時(shí)間復(fù)雜度應(yīng)為O(n2)。上面問(wèn)題中，若是改為從左上角沿線走到右下角再以不交叉的線路返回到出發(fā)點(diǎn)，算法應(yīng)該做怎樣的修改？原來(lái)的狀態(tài)

52、已經(jīng)不能保證“不交叉”，在這種狀況下，我們用增加一維狀態(tài)量的方法，以討論是否交叉，比較方便的思路從左上角出發(fā)兩條路，再向右下方遞推的過(guò)程中，兩條路的最末端始終不能是同一點(diǎn)，必須分布在這一階段的兩點(diǎn)上，直到最后在右下角匯合。由于增加了一維狀態(tài)量，時(shí)間復(fù)雜度變?yōu)镺(n3)。f.0-1 背包：巧妙地選取狀態(tài)量有時(shí)，選定狀態(tài)時(shí)發(fā)現(xiàn)不能使用動(dòng)態(tài)規(guī)劃，或問(wèn)題從表面上看讓人無(wú)所適從，我們不妨從另一個(gè)角度看問(wèn)題。上一章我們介紹了部分背包問(wèn)題，下面我們介紹更經(jīng)典的0-1背包問(wèn)題。問(wèn)題描述：有N 件物品和一個(gè)最大載重為M 的背包，每件物品都有相應(yīng)的重量和價(jià)值。現(xiàn)要求給出一個(gè)存放方案，使背包中物品總價(jià)值最大。所涉及

53、到的數(shù)字均為整數(shù)。數(shù)據(jù)規(guī)模：1N100，1M10000。這個(gè)問(wèn)題與部分背包問(wèn)題的區(qū)別在于，物品只能整件放入，不能只取一部分。這樣，背包很可能會(huì)有部分載重量未利用。若用貪心法取單位重量?jī)r(jià)值高的，可能會(huì)使背包未利用的載重升高，得不到最優(yōu)方案?？紤]到數(shù)據(jù)規(guī)模，選用動(dòng)態(tài)規(guī)劃法。似乎只有“每考慮一件物品為一階段”的劃分方法?？墒侨绾未_定狀態(tài)？很多人想不到這個(gè)方法：以一個(gè)最大載重值為一個(gè)狀態(tài)。完整遞推思路計(jì)算將考慮了前i 個(gè)物品后，最大載重為j 的背包能取得的最大價(jià)值f(i,j)，這個(gè)過(guò)程是可由f(i-1,j)和f(i-1,j- gi)遞推而得。最后求出f(N,M)。動(dòng)態(tài)轉(zhuǎn)移方程f(i,j)=maxf(i

54、-1,j),f(i-1,j-gi)+vi,1iN,1jM（實(shí)現(xiàn)時(shí)注意對(duì)邊界情形的處理），其中g(shù)i、vi分別表示第i 件物品的重量、價(jià)值。時(shí)間復(fù)雜度為O(N*M)，可以接受。實(shí)現(xiàn)時(shí)要注意空間復(fù)雜度（N*M 的數(shù)組顯然是開(kāi)不出來(lái)的）。動(dòng)態(tài)規(guī)劃的空間消耗是很大的，往往比深度優(yōu)先搜索大得多。動(dòng)態(tài)規(guī)劃的算法，往往空間復(fù)雜度比時(shí)間復(fù)雜度少一維。下面是常見(jiàn)的一種降低儲(chǔ)存的方法（在第二章提到過(guò)）動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)時(shí)往往可表示成矩陣形式。若遞推矩陣中每一行的值只與上一行有關(guān)，輸出只和最末行有關(guān)，則可將奇數(shù)行儲(chǔ)存在第一行，偶數(shù)行儲(chǔ)存在第二行，降低空間復(fù)雜度。這里還有一種優(yōu)化方法2若遞推矩陣中每一行中某一列的值只與上一行

55、中這一列及位于其右的列的有關(guān)，輸出只和最末行有關(guān)，則可按從左到右的順序計(jì)算該行每一列的值，并覆蓋掉原值即可。上面的0-1背包問(wèn)題，實(shí)現(xiàn)時(shí)，面臨的情況與“優(yōu)化方法2”中的類似但又有區(qū)別每一行中某一列的值只與上一行中這一列及位于其左的列的有關(guān)。這樣，我們需要按從右到左的順序計(jì)算?？臻g復(fù)雜度O(M)。附件中給出0-1背包問(wèn)題的源代碼。背包問(wèn)題還有兩種。一種是完全背包問(wèn)題：在0-1背包的基礎(chǔ)上，每種物品可放入很多個(gè)。這個(gè)問(wèn)題也用動(dòng)態(tài)規(guī)劃法解決。你會(huì)發(fā)現(xiàn)，這個(gè)問(wèn)題實(shí)現(xiàn)時(shí)只與0-1背包差一點(diǎn)點(diǎn)它按從左到右的順序計(jì)算，而0-1背包按從右到左的順序計(jì)算。另一種有時(shí)也稱作完全背包問(wèn)題：在0-1背包的基礎(chǔ)上，要求

56、背包恰好達(dá)到載重。這個(gè)問(wèn)題留給讀者思考。20g.Bitonic 旅行：最佳的狀態(tài)轉(zhuǎn)化方式歷史上有一個(gè)著名的“貨郎擔(dān)問(wèn)題”（也叫“中國(guó)郵路問(wèn)題”）：已知n 個(gè)點(diǎn)兩兩間的距離，給出過(guò)這些定點(diǎn)的最短閉合回路。（有時(shí)把這n 個(gè)定點(diǎn)間距離定義為歐氏幾何平面上距離，稱“歐幾里德旅行商問(wèn)題”。）這個(gè)問(wèn)題是NP-難問(wèn)題，只能用搜索解決。后來(lái)，J. L. Bentley 提出了這個(gè)問(wèn)題的變形Bitonic Tour 問(wèn)題（又稱雙調(diào)旅程問(wèn)題）。Bitonic 旅行：已知地圖上n 個(gè)旅行須到達(dá)的城市，要求從最西端的城市開(kāi)始，嚴(yán)格地由西向東到最東端的城市，再嚴(yán)格地由東向西回到出發(fā)點(diǎn)，除出發(fā)點(diǎn)外每個(gè)城市經(jīng)過(guò)且只經(jīng)過(guò)一次

57、。給出路程的最短值。數(shù)據(jù)規(guī)模：1n1000你可能會(huì)這么想：按旅行順序每過(guò)一個(gè)城市為一階段。可是這樣，狀態(tài)量需要記錄由東向西每一步所經(jīng)過(guò)的城市，時(shí)間復(fù)雜度O(2n)，與搜索無(wú)異！我們需要換一種狀態(tài)轉(zhuǎn)化方式。遞推思路從最東端開(kāi)始，找兩條到最西端的路徑。將地點(diǎn)按從東到西編號(hào)，每加入一個(gè)地點(diǎn)為一個(gè)階段。計(jì)算從地點(diǎn)i 到最東再到地點(diǎn)j 路程的最小值f(i,j)，這個(gè)過(guò)程是遞推的。最后求出minf(n,k)+distn,k。動(dòng)態(tài)轉(zhuǎn)移方程f(i,j)=f(i-1,j)+disti,i-1,1ji-2,inf(i,j)=f(i,j-1)+distj,j-1,1j=i-1,in（實(shí)現(xiàn)時(shí)注意對(duì)邊界情形的處理），其

58、中disti,j表示i 與j 間距離。時(shí)間復(fù)雜度為O(n2)，很好。附件中給出源代碼。h.最長(zhǎng)非降子序列模型NOIP 命題者還是比較仁慈的，考察動(dòng)態(tài)規(guī)劃時(shí)降低了難度，大多考察“模仿”，很少“構(gòu)造”NOIP 的動(dòng)態(tài)規(guī)劃題，很多都是在經(jīng)典問(wèn)題基礎(chǔ)上略作變化而成。下面這個(gè)問(wèn)題是我接觸到的變形題最泛濫的經(jīng)典問(wèn)題。最長(zhǎng)非降子序列：給定一串?dāng)?shù)，從中刪去一些數(shù)，使剩下的序列是非降的。求剩下的序列的最大長(zhǎng)度。數(shù)據(jù)規(guī)模：1n1000遞推思路f(i)表示對(duì)于前i 個(gè)數(shù)組成的序列，保留第i 個(gè)數(shù)時(shí)能取得的非降子序列的最大長(zhǎng)度。動(dòng)態(tài)轉(zhuǎn)移方程f(i)=maxf(j)+1,njni,1ji（實(shí)現(xiàn)時(shí)注意對(duì)邊界情形的處理），

59、其中ni表示序列中第i 個(gè)數(shù)的值。時(shí)間復(fù)雜度為O(n2)。說(shuō)明：實(shí)際上最長(zhǎng)非降子序列的最佳解法是二分法（但NOIP 要求的數(shù)據(jù)規(guī)模較小，往往可以用動(dòng)態(tài)規(guī)劃解）。最長(zhǎng)非降子序列的二分法會(huì)在第七章介紹?？纯聪旅孢@兩個(gè)問(wèn)題，你是不是覺(jué)得一下子就有了思路？合唱隊(duì)形（NOIP2004）N 位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K 位同學(xué)從左到右依次編號(hào)為1，2，K，他們的身高分別為T1，T2，TK，則他們的身高滿足T1TK(1=i& lt;=K)。你的任務(wù)是，已知所有N 位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的

60、同學(xué)排成合唱隊(duì)形。2N100，130Ti230。船（摘自?shī)W賽經(jīng)典）PALMIA 國(guó)家被一條河流分成南北兩岸，南北兩岸上各有N 個(gè)村莊。北岸的每一個(gè)村莊有一個(gè)唯一的朋友在南岸，且他們的朋友村莊彼此不同。每一對(duì)朋友村莊想要一條船來(lái)連接他們，他們向政府提出申請(qǐng)以獲得批準(zhǔn)。由于河面上常常有霧，政府決定禁止船只航線相交（如果相交，則很可能導(dǎo)致碰船）。你的任務(wù)是編寫(xiě)一個(gè)程序，幫助政府官員決定批準(zhǔn)哪些船只航線，使得不相交的航線數(shù)目最大。1N5000。對(duì)于“合唱隊(duì)形”，我們只需討論第i 人作最高點(diǎn)時(shí)，左邊升、右邊降序列長(zhǎng)度最大值。時(shí)間復(fù)雜度為21O(n3)。對(duì)于“船”，我們記ai為北岸第i 村對(duì)應(yīng)的南岸村莊的