動態(tài)規(guī)劃2014

1、動態(tài)規(guī)劃2014附中講義類型n資源分配（背包）n線性n區(qū)間n樹形n動規(guī)+貪心n動規(guī)+窮舉n其他一 資源問題 1 機器分配問題 n總公司擁有高效生產設備M臺，準備分給下屬的N個公司。各分公司若獲得這些設備，可以為國家提供一定的盈利。問：如何分配這M臺設備才能使國家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原則：每個公司有權獲得任意數目的設備，但總臺數不得超過總設備數M。n 數據文件格式為：第一行保存兩個數，第一個數是設備臺數M，第二個數是分公司數N。接下來是一個M*N的矩陣，表明了第I個公司分配J臺機器的盈利。 n用機器數來做狀態(tài)，數組FI，J表示前I個公司分配J臺機器的最大盈

2、利。則狀態(tài)轉移方程為:nFI,j:=max(fi-1,k+wi,j-k) 2 01背包問題 n一個旅行者有一個最多能用M公斤的背包，現在有N件物品，它們的重量是Wi,它們的價值為Pi。若每種物品只有一件求旅行者能獲得最大總價值。輸入格式：M,NW1,P1W2,P2.輸出格式： X ncij數組保存了1,2,3號物品依次選擇后的最大價值.nf(n,m)=maxf(n-1,m), f(n-1,m-wn)+Pn3 系統(tǒng)可靠性(完全背包) n有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c，價值是w。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大

3、。 n Fi,j:=maxfi-1,j-ci*k+k*wi nK=0j系統(tǒng)可靠性 n一個系統(tǒng)由若干部件串聯而成，只要有一個部件故障，系統(tǒng)就不能正常運行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動進入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？n給定一些系統(tǒng)備用件的單價Ck，以及當用Mk個此備用件時部件的正常工作概率PkMk，總費用上限C。n求系統(tǒng)可能的最高可靠性。n輸入文件格式：n第一行： n C n第二行： C1 P10 P11 P1X1 (0=X1=C/Ck) n n第 n 行： Cn Pn0 Pn1 P

4、nXn （0=Xn=C/Cn ）n輸入： 2 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 n輸出： 0.6375 nFI,money:將將money的資金用到前的資金用到前I項備用件中可項備用件中可得的最大可靠性，得的最大可靠性， nFI,money=maxFI-1,moneyk*CI +PI, k (0=I=n, 0=K= money div Cost(I) ) nF0,0 =0 nFn,C?4 金明的預算方案 n金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的

5、是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子： 主件 附件 電腦 打印機，掃描儀 書柜 圖書 書桌 臺燈，文具 工作椅 無n如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西很多， 肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數15表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是 10元的整數倍）。他希望在不

6、超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。n設第j件物品的價格為vj，重要度為wj，共選中了k件物品，編號依次為j1，j2，jk，則所求的總和為：nvj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號） n請你幫助金明設計一個滿足要求的購物單。n第1行，N m (N32000表示總錢數，m60為希望購買物品的個數。) 從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有3個非負整數 v p q (v0，所屬主件的編號）n輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（200000）。n【輸入樣例】 10

7、00 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【輸出樣例】 2200 n“每個主件可以有個，個或個附件”。降低復雜度。n對于一套物品（包含主件，所有的附件），我們稱為一個類，對一個類的物品的購買方法，有以下種：.一個都不買.主件.主件附件.主件附件.主件附件附件n把物品的類作為dp的狀態(tài)。fi,j=maxfi-1,j;fi-1,j-vi,0+vi,0*wi,0;fi-1,j-vi,0-vi,1+vi,0*wi,0+vi,1*wi,1;fi-1,j-vi,0-vi,2+vi,0*wi,0+vi,2*wi,2;fi-1,j-vi,0-vi,1-vi,2+

8、vi,0*wi,0+vi,1*wi,1+vi,2*wi,2;n時間復雜度O(n2)，空間復雜度O(n2)，n“每件物品都是10元的整數倍” 5 化工場裝箱員 n118號工廠是世界唯一秘密提煉锎的化工廠，由于提煉锎的難度非常高，技術不是十分完善，所以工廠生產的锎成品可能會有3種不同的純 度，A：100%，B：1%，C：0.01%，為了出售方便，必須把不同純度的成品分開裝箱，裝箱員grant第1次順序從流水線上取10個成品（如果一 共不足10個，則全部取出），以后每一次把手中某種純度的成品放進相應的箱子，然后再從流水線上順序取一些成品，使手中保持10個成品（如果把剩下的全部 取出不足10個，則全部

9、取出），如果所有的成品都裝進了箱子，那么grant的任務就完成了。n由于裝箱是件非常累的事情，grant希望他能夠以最少的裝箱次數來完成他的任務，現在他請你編個程序幫助他。nworker.in11ABCABCABCABnworker.out3nfst,a,b,c 到到st這個位置時，剩余這個位置時，剩余A（a個），個），B（b個），個），C（c個），個）， nfst,a1,b1,c1:=min(fst,a1,b1,c1,dfs(st,0,b1,c1)+1，dfs(st,a1,0,c1)+1，dfs(st,a1,b1,0)+1); 6 背包問題n你剛剛繼承了流行的“破鑼搖滾”樂隊錄制的尚未發(fā)表的

10、N(1 = N = 20)首歌的版權。你打算從中精選一些歌曲，發(fā)行M(1 = M = 20)張CD。每一張CD最多可以容納T(1 = T = 20)分鐘的音樂，一首歌不能分裝在兩張CD中。 n不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術價值。于是你決定根據以下標準進行選擇： n歌曲必須按照創(chuàng)作的時間順序在CD盤上出現。選中的歌曲數目盡可能地多。n第一行： 三個整數：N, T, M. 第二行： N個整數，分別表示每首歌的長度，按創(chuàng)作時間順序排列。n一個整數，表示可以裝進M張CD盤的樂曲的最大數目。 n4 5 24 3 4 236 背包問題 n多個背包，不可以重復放物品，但放物品的順序有限制。

11、nFI,j,k表示決策到第i個歌曲、第j個CD，用了k分鐘的空間，能刻的最多歌曲數。nfI,j,k:=max(fI-1,j,k,fI-1,j,k-Li+1,fi-1,j-1,t-Li)7 裝箱問題(判定性01背包) n有個容量為有個容量為c 的箱子和的箱子和n 個待裝載入箱子中的物品。個待裝載入箱子中的物品。物品物品i 需占用需占用si個單元（個單元（0sic）。成功裝載是）。成功裝載是指剩余空間最大。指剩余空間最大。nfj:=(fj or fj-v)n某運輸公司要把包裹裝入卡車中，每個包裹都有某運輸公司要把包裹裝入卡車中，每個包裹都有一定的重量，且每輛卡車也有其載重限制（假設一定的重量，且每

12、輛卡車也有其載重限制（假設每輛卡車的載重都一樣）。在卡車裝載問題中，每輛卡車的載重都一樣）。在卡車裝載問題中，希望用最少的卡車來裝載包裹。希望用最少的卡車來裝載包裹。8 背包問題(+-1背包問題+回溯)n給出一列數,可以對這列數進行一種操作con(a1,a2.an,c)表示把a1,a2.an這列數中的ac,a(c+1)取出,再把ac-a(c+1)放回原處,顯然,每操作一次序列長度減1.求一個長度為n-1的操作順序,使得第一個操作以初始序列為操作對象,從第二個操作開始每個操作都以上一個操作得到的序列為操作對象,并使得最后剩下的數為t.可以假定對于輸入至少有一個可行的操作序列.n1=N=100,n

13、-10000=T=10000n1=ai=1008 背包問題(+-1背包問題+回溯)Subtract.inSubtract.out4 510 2 5 21 2 15 412 10 4 3 52 3 2 18 背包問題(+-1背包問題+回溯) ndij表示前i個數獲得j結果是否可能ndij=di-1j-ai-1|di-1j+ai-1動態(tài)規(guī)劃解決問題的基本特征1. 動態(tài)規(guī)劃一般解決最值（最優(yōu)，最大，最小，最長）問題；2. 動態(tài)規(guī)劃解決的問題一般是離散的，可以劃分階段的；3. 動態(tài)規(guī)劃解決的問題必須包含最優(yōu)子結構，即可以由（n1）的最優(yōu)推導出n的最優(yōu)n1. 刻畫最優(yōu)解的結構特性. （一維，二維，三維數

14、組） 2. 遞歸的定義最優(yōu)解. （狀態(tài)轉移方程） 3. 以自底向上的方法來計算最優(yōu)解. 4. 從計算得到的解來構造一個最優(yōu)解.動態(tài)規(guī)劃的4個步驟排隊買票問題n 一場演唱會即將舉行?，F有n個歌迷排隊買票，一個人買一張，而售票處規(guī)定，一個人每次最多只能買兩張票。假設第i位歌迷買一張票需要時間Ti（1in），隊伍中相鄰的兩位歌迷（第j個人和第j+1個人）也可以由其中一個人買兩張票，而另一位就可以不用排隊了，則這兩位歌迷買兩張票的時間變?yōu)镽j，假如RjTj+Tj+1，這樣做就可以縮短后面歌迷等待的時間，加快整個售票的進程。現給出n, Tj和Rj，求使每個人都買到票的最短時間和方法。如果前如果前i個人買

15、票的最優(yōu)買票方式一確定，個人買票的最優(yōu)買票方式一確定，比如第比如第i個人買一張票，則前個人買一張票，則前i-1個人的買個人的買票方式也一定是最優(yōu)的。即問題的最優(yōu)票方式也一定是最優(yōu)的。即問題的最優(yōu)解包含子問題的最優(yōu)解。解包含子問題的最優(yōu)解。12345iin-1nn-2步驟步驟1：用用F（i）表示前）表示前i個人買票的最優(yōu)方個人買票的最優(yōu)方式，即所需最短時間；式，即所需最短時間； （1）第i個人的票自己買 （2）第i個人的票由第i-1個人買步驟步驟2：狀態(tài)轉移方程：狀態(tài)轉移方程：min步驟步驟3：以自底向上的方法來計算最優(yōu)解以自底向上的方法來計算最優(yōu)解1100 1min 1, 2iiif iTif

16、 iT f iR-=-+-+ 二、線性動態(tài)規(guī)劃n經典n最長不下降序列n數字三角形1.攔截導彈n某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導

17、彈。有可能不能攔截所有的導彈。n輸入描述輸入描述n導彈依次飛來的高度（雷達給出的高度數據是不大于導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數）的正整數）n輸出描述輸出描述n計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。多少套這種導彈攔截系統(tǒng)。n樣例輸入樣例輸入n389 207 155 300 299 170 158 65 n給定給定N個數個數q求最長的不上升子序列長度求最長的不上升子序列長度q求最少有多少個不上升序列能覆蓋所有的數，求最少有多少個不上升序列能覆蓋所有的數，即求最

18、少覆蓋序列。即求最少覆蓋序列。nN=10000.分析n設設f(i)表示前表示前i個數的最長不上升序列的長度。個數的最長不上升序列的長度。則則,f(i)=maxf(j)+1,其中其中j=ai這里這里0ji=n。顯然時間復雜度為顯然時間復雜度為O(n2)。n上述式子的含義：找到上述式子的含義：找到i之前的某之前的某j，這個數不比，這個數不比第第i個數小個數小,對于所有的對于所有的j取取f(j)的最大值。的最大值。 優(yōu)化n分析樣例分析樣例 n這里找這里找j,是在是在1i之間進行尋找，那么我們能否快速查找到我們所要更之間進行尋找，那么我們能否快速查找到我們所要更改的改的j呢呢?n要能更改需要兩個條件：

19、要能更改需要兩個條件：qj=aiqf(j)盡可能大盡可能大 n以上兩個條件提示我們后面的值一定要小于等于前面的值。因此我們以上兩個條件提示我們后面的值一定要小于等于前面的值。因此我們試著構建一個下降的序列。在這個下降的序列中查找可以更改的試著構建一個下降的序列。在這個下降的序列中查找可以更改的f值值,使得序列的值盡可能大。使得序列的值盡可能大。i1234567838920715530029917015865f12323456n具體過程：i1234567838920715530029917015865第第1次次389第第2次次389207第第3次次389207155第第4次次389300155（

20、由于（由于207300389,因此更新）因此更新）第第5次次389300299（由于（由于155299300,因此更新）因此更新）第第6次次389300299170第第7次次389300299170158第第8次次38930029917015865思考？n對于該序列，為什么要保留較大的值呢？對于該序列，為什么要保留較大的值呢？nf(i)=maxf(j)+1,其中其中j=ai該式子表示找前面的一個最大該式子表示找前面的一個最大f的符合條件的的符合條件的j，因此只要保存符合條，因此只要保存符合條件的最大的件的最大的j就可以了。就可以了。n在在f值相同的情況下，保留較大的數顯然更好。因為后面的數若能

21、跟較值相同的情況下，保留較大的數顯然更好。因為后面的數若能跟較小的數構成下降序列也一定能能較大的數構成下降序列，反之則不一小的數構成下降序列也一定能能較大的數構成下降序列，反之則不一定。例如定。例如207與與300的的f=2,但但207不能與不能與299構成下降序列，而構成下降序列，而300則可以。則可以。因為生成的序列為有序序列，因此我們可以采用二分查找的方法很快因為生成的序列為有序序列，因此我們可以采用二分查找的方法很快查找到更新的值，時間復雜度為查找到更新的值，時間復雜度為O(nn)求導彈的最小覆蓋n第二問很容易想到貪心法：那就是采取多次求最長不上升序列的辦法，然后得出總次數。n上述貪心

22、法不正確，很容易就能舉出反例。例如： “7 5 4 1 6 3 2”用多次求最長不上升序列所有為“7 5 4 3 2”、“1”、“6”共3套系統(tǒng)；但其實只要2套，分別為： “7 5 4 1”與“6 3 2”。n那么，正確的做法又是什么呢？ 解決解決n最少多少套系統(tǒng)最少多少套系統(tǒng) = 最長導彈高度上升序列長度。最長導彈高度上升序列長度。n知道了怎樣求最長不上升算法，同樣也就知道了知道了怎樣求最長不上升算法，同樣也就知道了怎樣求最長上升序列。怎樣求最長上升序列。n時間復雜度時間復雜度O(nn)。輸入一個長度為的整數序列（輸入一個長度為的整數序列（A1,A2,An），從中找出），從中找出一段長度不超

23、過一段長度不超過m的連續(xù)的子序列，使得這個序列的和最大。的連續(xù)的子序列，使得這個序列的和最大。例如：序列例如：序列 1， -3， 5， 1， -2， 3當當M=2或或3時時,S=5+1=6當當M=4時時,S=5+1-2+3=7數據范圍數據范圍: 50%的數據的數據N,M=1000 100%的數據的數據N,M=200002、最大子序和最大子序和 輸入一個長度為的整數序列（A1,A2,An），從中找出一段連續(xù)的子序列，使得這個序列的和最大。 和原問題相比沒有M這個序列長度的限制！一個簡化的問題序列的最大連續(xù)和 設設 F(i)表示以第表示以第i個數結尾的最大連續(xù)和個數結尾的最大連續(xù)和 以第以第i個數

24、結尾的最大連續(xù)和序列，可能存在兩種選擇：個數結尾的最大連續(xù)和序列，可能存在兩種選擇： 情形一：只包含情形一：只包含Ai 情形二：包含情形二：包含Ai和以和以Ai-1結尾的最大連續(xù)和序列結尾的最大連續(xù)和序列狀態(tài)轉移方程如下：狀態(tài)轉移方程如下： F(i)=maxAi , F(i-1)+Ai邊界：邊界：F(1)=A1，Ans=maxF(i)|1=i=n該算法的時間復雜度為該算法的時間復雜度為O(n)分析設 F(i)為以Ai結尾長度不超過M的最大子序和 ikijjmkAiF11|max)(? 對于每個F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時間復雜度為O(n3)算法一 枚舉ik

25、ijjmkAiF1.1|max)(i1jjA) i (S令.1| )(min)(.1| )()(maxmkkiSiSmkkiSiS簡化方程 用一個二叉堆來維護用一個二叉堆來維護S(i-k)，每次求，每次求F(i)之前的操作如之前的操作如下：下：.1| )(min)()(mkkiSiSiF求求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).復雜度復雜度O(2log2n)從堆中取出當前最小值從堆中取出當前最小值.復雜度復雜度O(1) 所以計算的總復

26、雜度為所以計算的總復雜度為O(nlog2n)算法二 堆優(yōu)化 在算法二中，考慮用隊列來維護決策值在算法二中，考慮用隊列來維護決策值S(i-k)。每次只需要在隊首刪掉每次只需要在隊首刪掉S(i-m-1)，在隊尾添加，在隊尾添加S(i-1) 。但是取最小值操作還是需要。但是取最小值操作還是需要O(n)時間復雜度時間復雜度的掃描。的掃描。 考察在添加考察在添加S(i-1)的時候，設現在隊尾的元素是的時候，設現在隊尾的元素是S(k)，由于，由于ki-1，所以，所以S(k)必然比必然比S(i-1)先出隊。先出隊。若此時若此時S(i-1)=S(k)，則，則S(k)這個決策永遠不會在以這個決策永遠不會在以后用

27、到，可以將后用到，可以將S(k)從隊尾刪除掉（此時隊列的尾從隊尾刪除掉（此時隊列的尾部形成了一個類似棧的結構）部形成了一個類似棧的結構）算法三 隊列優(yōu)化 同理，若隊列中兩個元素同理，若隊列中兩個元素S(i)和和S(j)，若若i=S(j)，則我們可以刪掉，則我們可以刪掉S(i)（因為（因為S(i)永遠不會被用到）。此時的隊永遠不會被用到）。此時的隊列中的元素構成了一個單調遞增的序列，列中的元素構成了一個單調遞增的序列，即：即：S1S2S3Sk隊列優(yōu)化用隊列維護S(i-k)所需要的操作： 若當前隊首元素S(x)，有x=i-m為止。 若當前隊尾元素S(k)=S(i-1)，則S(k)出隊；直到S(k)

28、S(i-1)為止。 在隊尾插入S(i-1) 取出隊列中的最小值，即隊首元素。算法三對于求每個對于求每個F(i)的時候，進隊和出隊的元的時候，進隊和出隊的元素不止一個。素不止一個。每一個元素每一個元素S(i)只進隊一次、出隊一次，只進隊一次、出隊一次，所以隊列維護的時間復雜度是所以隊列維護的時間復雜度是O(n)。而每。而每次求次求F(i)的時候取最小值操作的復雜度是的時候取最小值操作的復雜度是O(1)，所以這一步的總復雜度也是，所以這一步的總復雜度也是O(n)。 綜上所述，該算法的總復雜度是綜上所述，該算法的總復雜度是O(n)算法三3、理想收入問題、理想收入問題n理想收入是指在股票交易中，以理想

29、收入是指在股票交易中，以1元為本金可能獲元為本金可能獲得的最高收入，并且在理想收入中允許有非整數得的最高收入，并且在理想收入中允許有非整數股票買賣。股票買賣。n已知股票在第已知股票在第i天每股價格是天每股價格是Vi元，元，1iM，求，求M天后的理想收入。天后的理想收入。方法一方法一n設設Fi表示在第表示在第i天收盤時能達到的最高收入，則天收盤時能達到的最高收入，則有有Fi的遞推關系式：的遞推關系式：1010*/ max)0(VFiVkVjFiFikj，其中公式含義：在第公式含義：在第i天收盤時能達到的最高的收天收盤時能達到的最高的收入，是將第入，是將第j天收盤后的收入，全部用于買入天收盤后的收

30、入，全部用于買入第第k天的股票，再在第天的股票，再在第i天將所持的股票全部天將所持的股票全部賣出所得的收入。賣出所得的收入。時間復雜度是時間復雜度是O(M3)。方法二方法二n設設Pi表示前表示前i天能獲得的最多股票數，則可列出天能獲得的最多股票數，則可列出狀態(tài)轉移方程：狀態(tài)轉移方程：n設設Qi表示前表示前i天能達到的最大收入，則可列出狀天能達到的最大收入，則可列出狀態(tài)轉移方程：態(tài)轉移方程： / *,1max)0(iVjVjPiPiPij*/ ,1max)0(iVjVjQiQiQij時間復雜度是時間復雜度是O(M2)。方法三方法三n分析：上述公式的含義是當分析：上述公式的含義是當0=ji 時時,

31、求求Qi-1和和Qj*vi/vj的最大值的最大值 n對于對于0=ji，要求，要求Qi,實際上實際上Q1Qi-1都已經求出，因都已經求出，因此我們只要用一個變量保存此我們只要用一個變量保存Qj/Vj 的最大值即可，記為的最大值即可，記為MaxQ.n這樣，公式可以寫成這樣，公式可以寫成*/ ,1max)0(iVjVjQiQiQij*,1max)0(iVMAXQiQiQij 對每次求出的對每次求出的Qi,都更新都更新MaxQ,時間復雜度為時間復雜度為O(M)設有一個三角形的數塔，頂點結點稱為根結點，每個結點有一個整數數值。從頂點出發(fā)，可以向左走，也可以向右走。 問題：當三角形數塔給出之后，找出一條從

32、第一層到達底層的路徑，使路徑的問題：當三角形數塔給出之后，找出一條從第一層到達底層的路徑，使路徑的值最大。若這樣的路徑存在多條，任意給出一條即可。值最大。若這樣的路徑存在多條，任意給出一條即可。 回顧 數字三角形二維數組二維數組 D(X,y)描述問題，描述問題，D(X,y)表示從頂層到達第表示從頂層到達第X層第層第y個位置的最小路徑得分。個位置的最小路徑得分。階段分析：D(1,1)=13 到第x層的第y個位置有兩種可能，要么走右分支 得到，要么走左分支得到。n D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y)n D(1,1)a(1,1) 【問題背景】棧是計算機中經典的數據結

33、構，簡單的說，棧就是限制在一端進行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進棧）。一個操作數序列，1n，棧A的深度大于n?，F在可以進行兩種操作，1.將一個數，從操作數序列的頭端移到棧的頭端（對應數據結構棧的push操作）2. 將一個數，從棧的頭端移到輸出序列的尾端（對應數據結構棧的pop操作）4、棧使用這兩種操作，由一個操作數序列就可以得到一系列的輸使用這兩種操作，由一個操作數序列就可以得到一系列的輸出序列，下圖所示為由出序列，下圖所示為由1 2 3生成序列生成序列2 3 1的過程。的過程。111231233222323113你的程序將對

34、給定的你的程序將對給定的n，計算并輸出由操作數序列，計算并輸出由操作數序列1，2，n經過操作可能得到的輸出序列的總數。經過操作可能得到的輸出序列的總數。【輸入格式輸入格式】輸入文件只含一個整數輸入文件只含一個整數n（1n18）【輸出格式輸出格式】輸出文件只有一行，即可能輸出序列的總數目輸出文件只有一行，即可能輸出序列的總數目【輸入樣例輸入樣例】3【輸出樣例輸出樣例】55、火車進站、火車進站n給定給定N輛火車輛火車q第第i輛火車的進站時間輛火車的進站時間arrive(i)q第第i輛火車的離站時間輛火車的離站時間leave(i)n車站只能容納車站只能容納M輛火車輛火車n求最多能接受多少輛火車？求最

35、多能接受多少輛火車？nM=3q第第1，2，3輛分別進入（輛分別進入（ 1 2 3 ）；）；q第第2輛離開，可以看出要離開時，被第輛離開，可以看出要離開時，被第1輛火車卡在前面，因此第輛火車卡在前面，因此第1輛輛火車不能進入，隊列為（火車不能進入，隊列為（2 3）q第第2輛離開，第輛離開，第4輛進入（輛進入（3 4）q第第3，4輛離開，隊列空輛離開，隊列空q第第5，6輛進入輛進入 （5 6）q第第5，6分別離開，隊列空分別離開，隊列空l因此答案為因此答案為5輛輛123456分析n按到達時間排序和離開時間排序，這樣每一輛火車用線段按到達時間排序和離開時間排序，這樣每一輛火車用線段描述，有：描述，有

36、：q排在前面的火車，其進站時間必須先于排在后排在前面的火車，其進站時間必須先于排在后面的火車；面的火車；q排在前面的火車，其出站時間必須先于排在后排在前面的火車，其出站時間必須先于排在后面的火車，否則該列火車就要先進后出，不滿面的火車，否則該列火車就要先進后出，不滿足隊列特點。足隊列特點。n這樣對于任一列排序后的火車這樣對于任一列排序后的火車i，只有排在其后的火車才，只有排在其后的火車才有可能在它出站之后進站。接下來的任務便是采用動態(tài)規(guī)有可能在它出站之后進站。接下來的任務便是采用動態(tài)規(guī)劃方法求解了。劃方法求解了。m=1時時n設設fi表示第表示第i 列火車進站時，其后的火車最多列火車進站時，其后

37、的火車最多可以進站的數量，可以進站的數量， 則有：則有：nfi =maxfj+1，（滿足，（滿足i比比j先進站，且先進站，且j在在i 出站之后進站）；出站之后進站）；m=2n設設fi,j表示車站?？勘硎拒囌就？縤,j 兩列火車兩列火車(ij)時，其后的火車時，其后的火車（包括（包括i,j本身）最多可以進站的數量本身）最多可以進站的數量,則則:nfi,j=maxfj,k+1n條件：必須滿足按條件：必須滿足按i,j,k順序進站和出站，另外還要滿足順序進站和出站，另外還要滿足k在在i出站后且出站后且j 進站。進站。m=3n設設fi,j,k表示車站?？勘硎拒囌就？縤,j,k三列火車三列火車(ijk)時

38、，其后的火車時，其后的火車（包括（包括i,j,k）最多可以進站的數量。則有，）最多可以進站的數量。則有，nfi,j,k=maxfj,k,l+1n條件：必須滿足按條件：必須滿足按i,j,k,l順序進站和出站，另外還要滿足順序進站和出站，另外還要滿足l在在i 出站后進站。出站后進站。6、最長公共子序列、最長公共子序列n給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列，使得對所有的j=0，1，k-1，有xij = yj。n例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。n給出兩個字串S1和S2，長度不超過5000.n求這兩個串的最長公共子串長度。nX = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B)nY = (B, D, C, A, B, A) Y = (B, D,