1、常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃初步,JSOI2007夏令營B層次（泰州）,常州市第一中學(xué) 林厚從,問題：城市交通 有n個城市，編號1n，有些城市之間有路相連，有些則沒有，有路則當(dāng)然有一個距離?，F(xiàn)在規(guī)定只能從編號小的城市走到編號大的城市，問你從編號為1的城市走到編號為n的城市要花費的最短距離是多少？,輸入格式： 先輸入一個n，表示城市數(shù)，n100。 下面的n行，是一個n*n的鄰接矩陣map1.n,1.n。 mapi,j=0，表示城市i和城市j之間沒有路相連，否則為兩者之間的距離。 輸出格式： 一個數(shù)，表示從城市1走到城市n的最短距離。 輸入數(shù)據(jù)保證可以從城市1走到城市n。,動態(tài)規(guī)劃的引入,常州

2、市第一中學(xué) 林厚從,輸入樣例： 11 0 5 3 0 0 0 0 0 0 0 0 5 0 0 1 6 3 0 0 0 0 0 3 0 0 0 8 0 4 0 0 0 0 0 1 0 0 0 0 0 5 6 0 0 0 6 8 0 0 0 0 5 0 0 0 0 3 0 0 0 0 0 0 0 8 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 5 5 0 0 0 0 0 3 0 0 0 6 0 0 0 0 0 0 4 0 0 0 0 0 8 3 0 0 0 3 0 0 0 0 0 0 0 3 4 3 0,動態(tài)規(guī)劃的引入,常州市第一中學(xué) 林厚從,設(shè)一個數(shù)組dis1.n，disi表示城

3、市1到城市i的最短距離。題目就是要求disn。,根據(jù)題目的限制條件：只能從編號小的城市到編號大的城市。顯然，我們可以從城市1、城市2、城市n-1到城市n，前提是城市i與城市n之間有路，其中i=1，2，3，n-1。,所以，disn就應(yīng)該取disi+mapi，n中的最小值，且要求mapi，n0，i=1，2，3，n-1。,也就是說要求disn，就必須先求出dis1disn-1，類似于遞推算法中的“倒推法”，那么如何求disn-1呢？ disn-1 = min disi + mapi，n-1 且要求mapi，n-10，in-1。,城市交通分析,常州市第一中學(xué) 林厚從,現(xiàn)在我們把問題一般化，如何求dis

4、i呢？其中，i=1.n。,Disi = min disj + mapj，i,要滿足：mapj，i0，j=1.i-1,這是一個類似于遞歸的公式，意思為：要求disn就要先求disn-1 dis1，要求disn-1就要先求disn-2 dis1，而要求disi，就要先求disi-1 dis1，而dis1=0。在具體計算的時候，只要從dis1開始“順推”下去，依次求出dis2、 dis3、 disn-1 、disn即可。,城市交通分析,常州市第一中學(xué) 林厚從, dis1:=0; for i:=2 to n do begin min:=maxint; 用打擂臺的方法求出最小值 for j:=1 to

5、i-1 do if mapj,i0 then if disj+mapj,imin then min:=disj+mapj,i; disi:=min; end; writeln(min=,disn);,城市交通分析,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃是運籌學(xué)的一個分支。它是解決多階段決策過程最優(yōu)化問題的一種方法。1951年，美國數(shù)學(xué)家R.Bellman提出了解決這類問題的“最優(yōu)化原則”，1957年發(fā)表了他的名著動態(tài)規(guī)劃，該書是動態(tài)規(guī)劃方面的第一本著作。動態(tài)規(guī)劃問世以來，在工農(nóng)業(yè)生產(chǎn)、經(jīng)濟(jì)、軍事、工程技術(shù)等許多方面都得到了廣泛的應(yīng)用，取得了顯著的效果。 動態(tài)規(guī)劃運用于信息學(xué)競賽是在90年代初期，它以

6、獨特的優(yōu)點獲得了出題者的青睞。此后，它就成為了信息學(xué)競賽中必不可少的一個重要方法，幾乎在所有的國內(nèi)和國際信息學(xué)競賽中，都至少有一道動態(tài)規(guī)劃的題目。所以，掌握好動態(tài)規(guī)劃，是非常重要的。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃簡介,動態(tài)規(guī)劃中有很多深奧的概念，使用動態(tài)規(guī)劃也有很多前提條件，它與遞推、遞歸也有著密切的聯(lián)系，這些都要等到我們有一點編程經(jīng)歷后才好談起，所以，我們先放開這些理論，不要被這些理論嚇倒，而是去嘗試分析和解決幾個經(jīng)典動態(tài)規(guī)劃題目。 學(xué)習(xí)動態(tài)規(guī)劃最重要的是“一種思想方法和解題過程”，請大家積極動腦動手，跟著我一起分析和體會其中的方法和過程，然后再獨立去思考和實踐。,常州市第一中學(xué) 林厚從

7、,動態(tài)規(guī)劃簡介,攔截導(dǎo)彈（NOIP1999） 問題描述： 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈的枚數(shù)和導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，每個數(shù)據(jù)之間有一個空格），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈？如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)？,樣例輸入： 8 389 207 155 300 299 170 158 65

8、樣例輸出： 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）,常州市第一中學(xué) 林厚從,“攔截導(dǎo)彈”問題分析,先討論第一問：假設(shè)ai表示攔截的最后一枚導(dǎo)彈是第i枚時，系統(tǒng)能攔得的最大導(dǎo)彈數(shù)。例如，樣例中的a5=3，表示：如果系統(tǒng)攔截的最后一枚導(dǎo)彈是高度為299的話，最多可以攔截第1枚（389）、第4枚（300）、第5枚（299）三枚導(dǎo)彈。 顯然，a1a8中的最大值就是第一問的答案。關(guān)鍵是怎樣求得a1a8？,我們換一個角度，假設(shè)現(xiàn)在已經(jīng)求得a1a7（注：在動態(tài)規(guī)劃中，這樣的假設(shè)往往是很必要的），那么怎樣求a8呢？,a8要求系統(tǒng)攔截的最后1枚導(dǎo)彈必須是65，也就意味著倒數(shù)第2枚被攔截

9、的導(dǎo)彈高度必須不小于65，則符合要求的導(dǎo)彈有389、207、155、300、299、170、158。,常州市第一中學(xué) 林厚從,假如攔截的倒數(shù)第2枚導(dǎo)彈是300，則a8=a4+1；假如攔截的倒數(shù)第2枚導(dǎo)彈是299，則a8=a5+1；類似地，a8還可能是a1+1、a2+1、。當(dāng)然，我們現(xiàn)在要求得是以65結(jié)尾的最多導(dǎo)彈數(shù)目，因此a8要取所有可能值的最大值，即：a8 = max a1+1，a2+1，a7+1 = maxai + 1 (i=1.7)。,類似地，我們可以假設(shè)a1a6為已知，來求得a7。同樣，a6、a5、a4、a3、a2也是類似求法，而a1就是1，即如果系統(tǒng)攔截的最后1枚導(dǎo)彈是389，則只能

10、攔截第1枚。,“攔截導(dǎo)彈”問題分析,常州市第一中學(xué) 林厚從,這樣，求解過程可以用下列式子歸納： a1=1 ai=maxaj + 1 其中：i1，j=1.i-1，且hj=hi,第一問的答案就是a1a8中的最大值。,“攔截導(dǎo)彈”問題分析,常州市第一中學(xué) 林厚從,longest1:=1; for i:=2 to n do 分階段求出每步的最優(yōu)值 begin maxlong:=1; for j:=1 to i-1 do if himaxlong then maxlong:=longestj+1; longesti:=maxlong end; maxlong:=longest1; 以下打擂臺求出最大值

11、for i:=2 to n do if longestimaxlong then maxlong:=longesti; writeln(max=,maxlong);,這種解題方法就稱為“動態(tài)規(guī)劃”,“攔截導(dǎo)彈”問題分析,常州市第一中學(xué) 林厚從,“攔截導(dǎo)彈”問題分析,關(guān)于第二問： 由于它緊接著第一問，所以很容易受前面的影響，多次采用第一問的辦法，然后得出總次數(shù)，其實這是不對的。要舉反例并不難，比如長為7的高度序列“7 5 4 1 6 3 2”， 最長不上升序列為“7 5 4 3 2”，用多次求最長不上升序列的結(jié)果為3套系統(tǒng)；但其實只要2套，分別擊落“7 5 4 1”與“6 3 2”。所以不能用多

12、次“動態(tài)規(guī)劃”的方法做，那么，正確的做法又是什么呢？,我們的目標(biāo)是用最少的系統(tǒng)擊落所有導(dǎo)彈，至于系統(tǒng)之間怎么分配導(dǎo)彈數(shù)目則無關(guān)緊要，上面錯誤的想法正是承襲了“一套系統(tǒng)盡量多攔截導(dǎo)彈”的思維定勢，忽視了最優(yōu)解中各個系統(tǒng)攔截數(shù)較為平均的情況，本質(zhì)上是一種貪心算法，但貪心的策略不對。如果從每套系統(tǒng)攔截的導(dǎo)彈方面來想行不通的話，我們就應(yīng)該換一個思路，從攔截某個導(dǎo)彈所選的系統(tǒng)入手。,常州市第一中學(xué) 林厚從,“攔截導(dǎo)彈”問題分析,題目告訴我們，已有系統(tǒng)目前的瞄準(zhǔn)高度必須不低于來犯導(dǎo)彈高度，所以，當(dāng)已有的系統(tǒng)均無法攔截該導(dǎo)彈時，就不得不啟用新系統(tǒng)。如果已有系統(tǒng)中有一個能攔截該導(dǎo)彈，我們是應(yīng)該繼續(xù)使用它，還是

13、另起爐灶呢？事實是：無論用哪套系統(tǒng)，只要攔截了這枚導(dǎo)彈，那么系統(tǒng)的瞄準(zhǔn)高度就等于導(dǎo)彈高度，這一點對舊的或新的系統(tǒng)都適用。而新系統(tǒng)能攔截的導(dǎo)彈高度最高，即新系統(tǒng)的性能優(yōu)于任意一套已使用的系統(tǒng)。既然如此，我們當(dāng)然應(yīng)該選擇已有的系統(tǒng)。如果已有系統(tǒng)中有多個可以攔截該導(dǎo)彈，究竟選哪一個呢？當(dāng)前瞄準(zhǔn)高度較高的系統(tǒng)的“潛力”較大，而瞄準(zhǔn)高度較低的系統(tǒng)則不同，它能打下的導(dǎo)彈別的系統(tǒng)也能打下，它夠不到的導(dǎo)彈卻未必是別的系統(tǒng)所夠不到的。所以，當(dāng)有多個系統(tǒng)供選擇時，要選瞄準(zhǔn)高度最低的使用，當(dāng)然瞄準(zhǔn)高度同時也要大于等于來犯導(dǎo)彈高度。,常州市第一中學(xué) 林厚從,“攔截導(dǎo)彈”問題分析,解題時用一個數(shù)組sys記下當(dāng)前已有系統(tǒng)

14、的各個當(dāng)前瞄準(zhǔn)高度，該數(shù)組中實際元素的個數(shù)就是第二問的解答。,sys1:=h1; tail:=1; for i:=2 to n do begin minheight:=maxint; for j:=1 to tail do 找一套最適合的系統(tǒng) if sysjhi then if sysjminheight then begin minheight:=sysj; select:=j end; if minheight=maxint 開一套新系統(tǒng) then begin tail:=tail+1; systail:=hi end else sysselect:=hi end; writeln(tot

15、al=,tail);,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃簡介,數(shù)字三角形（IOI1994） 問題描述 如下所示為一個數(shù)字三角形： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 請編一個程序計算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最大。規(guī)定： 每一步可沿直線向下或右斜線向下走； 1三角形行數(shù)100； 三角形中的數(shù)字為整數(shù)0，1，99；,樣例輸出： 30,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃簡介,分析數(shù)字三角形,1、窮舉法：最多100行，有299條路徑，超時；,2、貪心法：不正確；,3、動態(tài)規(guī)劃：,假設(shè)從頂至數(shù)字三角形的某一位置的所有路徑中，所經(jīng)過的數(shù)字的總和最大的那條路徑

16、，我們稱之為該位置的最大路徑。由于問題規(guī)定每一步只能沿直線向下或沿斜線向右下走，若要走到該位置，則其前一位置必為其左上方或正上方兩個位置之一，由此可知，當(dāng)前位置的最優(yōu)路徑必定與其左上方或正上方兩個位置的最優(yōu)路徑有關(guān)，且來自于其中更優(yōu)的一個。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃簡介,設(shè)ai，j表示數(shù)字三角形中第i行第j列的數(shù)，再設(shè)一個二維數(shù)組sum記錄每個位置的最優(yōu)路徑的數(shù)字總和，則：,sumi，j=maxsumi-1，j，sumi-1，j-1 + ai，j 其中：2=i=n，2=j=i,邊界條件： sumi，1=sumi-1，1+ai，1 第1列 sumi，i=sumi-1，i-1+ai，i 對

17、角線,這個問題呈現(xiàn)出明顯的階段性：三角形的每一行都是一個階段。對最大路徑的求解過程，實際上是從上往下不斷地按照階段的順序求解。對問題適當(dāng)?shù)貏澐蛛A段是動態(tài)規(guī)劃解題中的一個重要步驟。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃簡介,fillchar(sum,sizeof(sum),0); 初始化為0 sum1,1:=a1,1; for i:=2 to n do 逐行動歸 for j:=1 to i do if sumi-1,j-1sumi-1,j then sumi,j:=sumi-1,j-1+ai,j else sumi,j:=sumi-1,j+ai,j; ans:=0; 打擂臺求最優(yōu)值 for j:=1

18、 to n do if sumn,jans then ans:=sumn,j; writeln(ans);,Var sum:array1.maxn,0.maxn of longint;,程序中為什么沒考慮j=1或j=i的情況？,常州市第一中學(xué) 林厚從,思考題 假如本題還要你輸出最大值的那條路徑，即不僅要求出最優(yōu)值、還要你構(gòu)造出最優(yōu)方案，你怎么辦呢？,用1個三維數(shù)組 sum1.maxn,0.maxn,1.2來記憶最優(yōu)值及最優(yōu)值的來源，在遞推的同時記下路徑，即：sumx,y,1表示第x行、y列能夠取得的最大值，sumx,y,2表示該最大值是從上一行的哪個位置得來的（如-1表示從左上方得到的，0表示

19、從正上方得到的）。最后輸出時，從下往上倒過來推即可！,動態(tài)規(guī)劃簡介,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃的基本概念,1、階段 用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當(dāng)?shù)貏澐殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。階段的劃分一般是根據(jù)時間和空間的自然特征來定的，一般要便于把問題轉(zhuǎn)化成多階段決策的過程。,2、狀態(tài) 狀態(tài)表示的是事物某一階段的性質(zhì)，狀態(tài)通過一個變量來描述，這個變量稱為狀態(tài)變量。各個狀態(tài)之間是可以相互轉(zhuǎn)換的。,3、決策 對問題的處理中做出某種選擇性的行動就是決策。一個實際問題可能要有多次決策，在每一個階段中都需要有一次決策。 一次決策就會從一個階段進(jìn)入另一個階段，狀態(tài)也就發(fā)

20、生了轉(zhuǎn)移。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃的基本概念,4、策略和最優(yōu)策略 所有階段按照約定的決策方法，依次排列構(gòu)成問題的求解全過程。這些決策的總體稱為策略。在實際問題中，從決策允許集合中找出最優(yōu)效果的策略稱為最優(yōu)策略。,5、狀態(tài)轉(zhuǎn)移方程 前一階段的終點就是后一階段的起點，這種關(guān)系描述了由K階段到K+1階段狀態(tài)的演變規(guī)律，是關(guān)于兩個相鄰階段狀態(tài)的方程，稱為狀態(tài)轉(zhuǎn)移方程，是動態(tài)規(guī)劃的核心。,6、指標(biāo)函數(shù)和最優(yōu)化概念 用來衡量多階段決策過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)。它應(yīng)該在全過程和所有子過程中有定義、并且可度量。指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃的基本概念

21、,動態(tài)規(guī)劃所處理的問題是一個“多階段決策問題” 目的是得到一個最優(yōu)解（方案） 大概思想如下圖所示：,常州市第一中學(xué) 林厚從,運用動態(tài)規(guī)劃的條件,1、最優(yōu)化原理,作為整個過程的最優(yōu)策略具有：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略的性質(zhì)。也可以通俗地理解為：子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，非最優(yōu)解對問題的求解沒有影響。,比如前面的數(shù)字三角形問題，如果我們想求走到某一位置的最優(yōu)路徑，我們只需要知道其左上方或正上方兩個位置之一的最優(yōu)值，而不用考慮其它的路徑，因為其它的非

22、最優(yōu)路徑肯定對當(dāng)前位置的結(jié)果沒有影響。,常州市第一中學(xué) 林厚從,運用動態(tài)規(guī)劃的條件,1、最優(yōu)化原理,在數(shù)字三角形問題中，如果我們把問題稍微改變一下：將三角形中的數(shù)字改為-100100之間的整數(shù)，計算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最接近于零。,這個問題就不具有最優(yōu)子結(jié)構(gòu)性質(zhì)了，因為子問題最優(yōu)，即最接近于零，反而可能造成問題的解遠(yuǎn)離零，這樣的反例是不難構(gòu)造的，本問題就不能用動態(tài)規(guī)劃的方法解決了。,因此，并不是所有的“決策問題”都可以用“動態(tài)規(guī)劃”來解決。只有當(dāng)一個問題呈現(xiàn)出最優(yōu)子結(jié)構(gòu)時，“動態(tài)規(guī)劃”才可能是一個合適的侯選方法。,常州市第一中學(xué) 林厚從,運用動態(tài)規(guī)劃的條件,2、

23、無后效性原則,1、最優(yōu)化原理,所謂無后效性原則，指的是這樣一種性質(zhì)：某一階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說“未來與過去無關(guān)”。當(dāng)前的狀態(tài)是此前歷史的一個完整總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。 具體地說，如果一個問題被劃分各個階段之后，階段I中的狀態(tài)只能由階段I+1中的狀態(tài)轉(zhuǎn)移方程得來，與其他沒有關(guān)系，特別是與未發(fā)生的狀態(tài)沒有關(guān)系，這就是無后效性。,常州市第一中學(xué) 林厚從,運用動態(tài)規(guī)劃的條件,2、無后效性原則,1、最優(yōu)化原理,例如：給定一個平面上的n個點的坐標(biāo)，規(guī)定必須從最左邊一個點開始，嚴(yán)格地從左至右訪問到最右邊的點，再嚴(yán)格地由右向

24、左訪問到出發(fā)點，編程確定一條連接各個點的閉合的游歷路線，要求整個路程最短的路徑長度。,分析： 本題可以根據(jù)起點，終點劃分階段，且滿足無后效性原則，可以考慮用動態(tài)規(guī)劃做。 但如果把“規(guī)定必須從最左邊一個點開始，嚴(yán)格地從左至右訪問到最右邊的點，再嚴(yán)格地由右向左訪問到出發(fā)點”這個限制條件去掉，則階段與階段之間沒有什么必然的“順序”，而且把各個階段畫成一個圖后會出現(xiàn)“環(huán)路”，所以有“后效性”，就不能用動態(tài)規(guī)劃做了。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。這類問

25、題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最?。┙狻Ｈ舸嬖诙鄠€最優(yōu)解的話，它只取其中的一個。,動態(tài)規(guī)劃的基本概念,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃應(yīng)用舉例,例1、挖地雷（NOIP1996 ） 在一個地圖上有N個地窖（N=200），每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接路徑，并規(guī)定路徑都是單向的。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖地雷的方案，使他能挖到最多的地雷。,輸入 N 地窖的個數(shù) W1 W2WN 每個地窖中的地雷數(shù) X1 Y1 表示可從X1到Y(jié)1 X2 Y2 0 0 表示輸

26、入結(jié)束,輸出 K1K2Kv 挖地雷的順序 MAX 最多挖出的地雷數(shù),輸入： 6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0,輸出： 3-4-5-6 34,常州市第一中學(xué) 林厚從,挖地雷問題分析 設(shè)W（i）為第i個地窖所藏有的地雷數(shù)，A（i,j）表示第i個地窖與第j個地窖之間是否有通路，F(xiàn)（i）為從第i個地窖開始最多可以挖出的地雷數(shù)。,動態(tài)規(guī)劃應(yīng)用舉例,F（i）= MAX F(j) + W(i) ,(ij=n , A(i,j)=1),邊界：F（n）=W(n),于是就可以通過遞推的方法，從后（即F（n）往前逐個找出所有的F（i），再從中找一個最大的即

27、為第2問的解。 對于具體所走的路徑（第2問），可以通過一個向后的鏈接來實現(xiàn)。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃應(yīng)用舉例,例2、接蘋果(apples) 農(nóng)場的夏季是收獲的好季節(jié)。在John的農(nóng)場，他們用一種特別的方式來收蘋果：Bessie搖蘋果樹，蘋果落下，然后John盡力接到盡可能多的蘋果。作為一個有經(jīng)驗的農(nóng)夫，John將這個過程坐標(biāo)化。他清楚地知道什么時候(1=t=1,000,000)什么位置(用二維坐標(biāo)表示，-1000=x,y=1000)會有蘋果落下。他只有提前到達(dá)那個位置，才能接到那個位置掉下的蘋果。一個單位時間，John能走s(1=s=1000)個單位。假設(shè)他開始時(t=0)站在(0,

28、0)點，他最多能接到多少個蘋果？,輸入：第一行是兩個整數(shù)N(蘋果個數(shù)，N=5000)和S(速度)； 第2.N+1行：每行3個整數(shù)Xi,Yi,Ti，表示每個蘋果掉下 的位置和落下的時間。 輸出：僅一行，一個數(shù)，表示最多能接到幾個蘋果。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃應(yīng)用舉例,樣例 apples.in 5 3 0 0 1 0 3 2 -5 12 6 -1 0 3 -1 1 2 apples.out 3 說明：John可以接到第1,5,4個蘋果。,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃應(yīng)用舉例,接蘋果問題分析 首先劃分階段，很明顯，按照蘋果掉落的時間先后順序來劃分階段，所以有必要按時間從小到大給各個蘋果

29、排個序，并按順序標(biāo)上1.n的編號。,假如John現(xiàn)在正站在某個位置上接蘋果，為了使他到當(dāng)前為止接到的蘋果數(shù)最大，我們想要知道的是他前一步在哪個位置接蘋果，并且要知道到那個位置為止接到的蘋果最多是多少。,假設(shè)dis(i，j)表示第i個蘋果與第j個蘋果之間的直線距離。time(i)表示第i個蘋果掉落的時刻。F(i)表示John當(dāng)前站在第i個蘋果的位置上最多能接到的蘋果總數(shù)（包括他以前接的）。,F(i) = max F(j) + 1 其中0=j=i-1，且dis(i,j)=(time(i)-time(j)*S,初始條件：F(0)=0 表示John站在出發(fā)點(0,0)時一個蘋果也沒接到。,常州市第一中

30、學(xué) 林厚從,動態(tài)規(guī)劃應(yīng)用舉例,例3、低價購買（buylow） “低價購買”這條建議是在股票市場取得成功的一半規(guī)則。要想被認(rèn)為是偉大的投資者，你必須遵循以下的購買建議：低價購買，再低價購買。每次你購買一支股票，你必須用低于你上次購買它的價格購買它。買的次數(shù)越多越好! 你的目標(biāo)是在遵循以上建議的前提下，求你最多能購買股票的次數(shù)。 你將被給出一段時間內(nèi)一支股票每天的出售價(216范圍內(nèi)的正整數(shù))，你可以選擇在哪些天購買這支股票。每次購買都必須遵循“低價購買，再低價購買”的原則。 寫一個程序計算最大購買次數(shù)。 這里是某支股票的價格清單： 日期 1 2 3 4 5 6 7 8 9 10 11 12 價格 68 69 54 64 68 64 70 67 78 62 98 87 最優(yōu)秀的投資者可以購買最多4次股票，可行方案中的一種是： 日期 2 5 6 10 價格 69 68 64 62,常州市第一中學(xué) 林厚從,動態(tài)規(guī)劃應(yīng)用舉例,輸入 輸入共