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

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

2、利。則狀態(tài)轉(zhuǎn)移方程為:nFI,j:=max(fi-1,k+wi,j-k) 2 01背包問題 n一個旅行者有一個最多能用M公斤的背包，現(xiàn)在有N件物品，它們的重量是Wi,它們的價值為Pi。若每種物品只有一件求旅行者能獲得最大總價值。輸入格式：M,NW1,P1W2,P2.輸出格式： X ncij數(shù)組保存了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)由若干部件串聯(lián)而成，只要有一個部件故障，系統(tǒng)就不能正常運行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動進(jìn)入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？n給定一些系統(tǒng)備用件的單價Ck，以及當(dāng)用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 金明的預(yù)算方案 n金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的

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

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

7、00 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【輸出樣例】 2200 n“每個主件可以有個，個或個附件”。降低復(fù)雜度。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時間復(fù)雜度O(n2)，空間復(fù)雜度O(n2)，n“每件物品都是10元的整數(shù)倍” 5 化工場裝箱員 n118號工廠是世界唯一秘密提煉锎的化工廠，由于提煉锎的難度非常高，技術(shù)不是十分完善，所以工廠生產(chǎn)的锎成品可能會有3種不同的純 度，A：100%，B：1%，C：0.01%，為了出售方便，必須把不同純度的成品分開裝箱，裝箱員grant第1次順序從流水線上取10個成品（如果一 共不足10個，則全部取出），以后每一次把手中某種純度的成品放進(jìn)相應(yīng)的箱子，然后再從流水線上順序取一些成品，使手中保持10個成品（如果把剩下的全部 取出不足10個，則全部

9、取出），如果所有的成品都裝進(jìn)了箱子，那么grant的任務(wù)就完成了。n由于裝箱是件非常累的事情，grant希望他能夠以最少的裝箱次數(shù)來完成他的任務(wù)，現(xiàn)在他請你編個程序幫助他。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)首歌的版權(quán)。你打算從中精選一些歌曲，發(fā)行M(1 = M = 20)張CD。每一張CD最多可以容納T(1 = T = 20)分鐘的音樂，一首歌不能分裝在兩張CD中。 n不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術(shù)價值。于是你決定根據(jù)以下標(biāo)準(zhǔn)進(jìn)行選擇： n歌曲必須按照創(chuàng)作的時間順序在CD盤上出現(xiàn)。選中的歌曲數(shù)目盡可能地多。n第一行： 三個整數(shù)：N, T, M. 第二行： N個整數(shù)，分別表示每首歌的長度，按創(chuàng)作時間順序排列。n一個整數(shù)，表示可以裝進(jìn)M張CD盤的樂曲的最大數(shù)目。 n4 5 24 3 4 236 背包問題 n多個背包，不可以重復(fù)放物品，但放物品的順序有限制。

11、nFI,j,k表示決策到第i個歌曲、第j個CD，用了k分鐘的空間，能刻的最多歌曲數(shù)。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某運輸公司要把包裹裝入卡車中，每個包裹都有某運輸公司要把包裹裝入卡車中，每個包裹都有一定的重量，且每輛卡車也有其載重限制（假設(shè)一定的重量，且每

12、輛卡車也有其載重限制（假設(shè)每輛卡車的載重都一樣）。在卡車裝載問題中，每輛卡車的載重都一樣）。在卡車裝載問題中，希望用最少的卡車來裝載包裹。希望用最少的卡車來裝載包裹。8 背包問題(+-1背包問題+回溯)n給出一列數(shù),可以對這列數(shù)進(jìn)行一種操作con(a1,a2.an,c)表示把a1,a2.an這列數(shù)中的ac,a(c+1)取出,再把ac-a(c+1)放回原處,顯然,每操作一次序列長度減1.求一個長度為n-1的操作順序,使得第一個操作以初始序列為操作對象,從第二個操作開始每個操作都以上一個操作得到的序列為操作對象,并使得最后剩下的數(shù)為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個數(shù)獲得j結(jié)果是否可能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)子結(jié)構(gòu)，即可以由（n1）的最優(yōu)推導(dǎo)出n的最優(yōu)n1. 刻畫最優(yōu)解的結(jié)構(gòu)特性. （一維，二維，三維數(shù)

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

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

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

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

19、要能更改需要兩個條件：qj=aiqf(j)盡可能大盡可能大 n以上兩個條件提示我們后面的值一定要小于等于前面的值。因此我們以上兩個條件提示我們后面的值一定要小于等于前面的值。因此我們試著構(gòu)建一個下降的序列。在這個下降的序列中查找可以更改的試著構(gòu)建一個下降的序列。在這個下降的序列中查找可以更改的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值相同的情況下，保留較大的數(shù)顯然更好。因為后面的數(shù)若能

21、跟較值相同的情況下，保留較大的數(shù)顯然更好。因為后面的數(shù)若能跟較小的數(shù)構(gòu)成下降序列也一定能能較大的數(shù)構(gòu)成下降序列，反之則不一小的數(shù)構(gòu)成下降序列也一定能能較大的數(shù)構(gòu)成下降序列，反之則不一定。例如定。例如207與與300的的f=2,但但207不能與不能與299構(gòu)成下降序列，而構(gòu)成下降序列，而300則可以。則可以。因為生成的序列為有序序列，因此我們可以采用二分查找的方法很快因為生成的序列為有序序列，因此我們可以采用二分查找的方法很快查找到更新的值，時間復(fù)雜度為查找到更新的值，時間復(fù)雜度為O(nn)求導(dǎo)彈的最小覆蓋n第二問很容易想到貪心法：那就是采取多次求最長不上升序列的辦法，然后得出總次數(shù)。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) = 最長導(dǎo)彈高度上升序列長度。最長導(dǎo)彈高度上升序列長度。n知道了怎樣求最長不上升算法，同樣也就知道了知道了怎樣求最長不上升算法，同樣也就知道了怎樣求最長上升序列。怎樣求最長上升序列。n時間復(fù)雜度時間復(fù)雜度O(nn)。輸入一個長度為的整數(shù)序列（輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出），從中找出一段長度不超

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

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

25、ijjmkAiF1.1|max)(i1jjA) i (S令.1| )(min)(.1| )()(maxmkkiSiSmkkiSiS簡化方程 用一個二叉堆來維護(hù)用一個二叉堆來維護(hù)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).復(fù)雜度復(fù)雜度O(2log2n)從堆中取出當(dāng)前最小值從堆中取出當(dāng)前最小值.復(fù)雜度復(fù)雜度O(1) 所以計算的總復(fù)

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

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

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

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

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

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

32、第一層到達(dá)底層的路徑，使路徑的問題：當(dāng)三角形數(shù)塔給出之后，找出一條從第一層到達(dá)底層的路徑，使路徑的值最大。若這樣的路徑存在多條，任意給出一條即可。值最大。若這樣的路徑存在多條，任意給出一條即可。 回顧 數(shù)字三角形二維數(shù)組二維數(shù)組 D(X,y)描述問題，描述問題，D(X,y)表示從頂層到達(dá)第表示從頂層到達(dá)第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) 【問題背景】棧是計算機中經(jīng)典的數(shù)據(jù)結(jié)

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

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

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

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

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

38、，其后的火車時，其后的火車（包括（包括i,j,k）最多可以進(jìn)站的數(shù)量。則有，）最多可以進(jìn)站的數(shù)量。則有，nfi,j,k=maxfj,k,l+1n條件：必須滿足按條件：必須滿足按i,j,k,l順序進(jìn)站和出站，另外還要滿足順序進(jìn)站和出站，另外還要滿足l在在i 出站后進(jìn)站。出站后進(jìn)站。6、最長公共子序列、最長公共子序列n給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個嚴(yán)格遞增下標(biāo)序列，使得對所有的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,