線性類動(dòng)態(tài)規(guī)劃

1、最長上升序列 設(shè)有整數(shù)序列b1,b2,b3,bm，若存在下標(biāo)i1i2i3 in，且bi1bi2bi3 bin，則稱 b1,b2,b3,bm中有長度為n的上升序列bi1 , bi2 ,bi3 ,bin 。求序列b1,b2,b3,bm中所有長度(n)最大上升子序列輸入：整數(shù)序列。輸出：最大長度n和所有長度為n的序列個(gè)數(shù)。1分析設(shè)f(i)為前i個(gè)數(shù)中的最長上升序列長度 , 則f(i)=maxf(j)+1 (1=ji=m, bjbi)邊界為F(1)=12分析設(shè)t(i)為前i個(gè)數(shù)中最長不下降序列的個(gè)數(shù),則t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)+1) 初始為t(i)=1當(dāng)f

2、(i)=n時(shí)，將t(i)累加舉例： 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2答案：f=7時(shí)，邊界為t=43進(jìn)一步(3)求本質(zhì)不同的最長不下降序列個(gè)數(shù)有多少個(gè)？ 如：1 2 3 4 6 5 8 10 9 有， 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8 9 都是本質(zhì)不同的。 但對于 1 2 2 3 3 5 4 f ： 1 2 2 3 3 5 4 t： 1 1 1 2 2 4 4 答案有8個(gè)，其中4個(gè)1 2 3 5 ，4個(gè)1 2 3 44改進(jìn)算

3、法上例顯然對于相兩個(gè)相同的數(shù)，重復(fù)算了多次因此，我們對算法進(jìn)行改進(jìn)：對原序列按b從小到大（當(dāng)bi=bj時(shí)按F從大到小）排序，增設(shè)Order(i)記錄新序列中的i個(gè)數(shù)在原序列中的位置?？梢姡髏(i)時(shí)，當(dāng)f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)時(shí)，便不累加t(j)。這樣就避免了重復(fù)。 上述算法的時(shí)間復(fù)雜度為O(n2) 5添括號問題 有一個(gè)由數(shù)字1，2，. ，9組成的數(shù)字串（長度不超過200），問如何將M(M=20)個(gè)加號(+)插入到這個(gè)數(shù)字串中，使所形成的算術(shù)表達(dá)式的值最小。請編一個(gè)程序解決這個(gè)問題。注意：加號不能加在數(shù)字串的最前面或最末尾，也不應(yīng)有

4、兩個(gè)或兩個(gè)以上的加號相鄰。M保證小于數(shù)字串的長度。例如：數(shù)字串79846，若需要加入兩個(gè)加號，則最佳方案為79+8+46，算術(shù)表達(dá)式的值133。6分析考慮到數(shù)據(jù)的規(guī)模超過了長整型,我們注意在解題過程中采用高精度算法.規(guī)劃方程:FI,J = MIN FI-1,K + NUMK+1,J (I-1=K=J-1)邊界值:F0,I := NUM1,I;FI，J表示前J個(gè)數(shù)字中添上I個(gè)加號后得到的最小值。NUMI，J表示數(shù)字串第I位到第J位的數(shù)上述問題的每一步，都只與上一步有關(guān)。因此可以采用滾動(dòng)數(shù)組程序的時(shí)間效率約為 20 * 200 * 200 7演唱會一場演唱會即將舉行?，F(xiàn)有N（ON=200）個(gè)歌迷排

5、隊(duì)買票，一個(gè)人買一張，而售票處規(guī)定，一個(gè)人每次最多只能買兩張票。假設(shè)第I位歌迷買一張票需要時(shí)間Ti（1=I=n），隊(duì)伍中相鄰的兩位歌迷（第j個(gè)人和第j+1個(gè)人）也可以由其中一個(gè)人買兩張票，而另一位就可以不用排隊(duì)了，則這兩位歌迷買兩張票的時(shí)間變?yōu)镽j，(假如RjTj+Tj+1，則這樣做就可以縮短后面歌迷等待的時(shí)間，加快整個(gè)售票的進(jìn)程 )?，F(xiàn)給出N，Ti和Ri，求使每個(gè)人都買到票的最短時(shí)間和方法。8分析設(shè)f（i）為前i個(gè)人花費(fèi)最短時(shí)間于是有f（i）=minf（i-1）+Ti，f（i-2）+Ri-1，初始f（0）=0，f（1）=T19復(fù)制書稿假設(shè)有M本書（編號為1，2，M），想將每本復(fù)制一份，M本書

6、的頁數(shù)可能不同（分別是P1，P2，PM）。任務(wù)：將這M本書分給K個(gè)抄寫員(K=M) 每本書只能分配給一個(gè)抄寫員進(jìn)行抄寫，而每個(gè)抄寫員所分配到的書必須是連續(xù)順序的。10分析設(shè)F（I，J）為前I個(gè)抄寫員復(fù)制前J本書的最小“頁數(shù)最大數(shù)”。于是有 F（I，J）=MINmax F（I-1，V），T（V+1，J） （1=I=K，I=J=M-K+I，I-1=V=J-1。 其中T（V+1，J）表示從第V+1本書到第J本書的頁數(shù)和。起步時(shí)F（1，1）=P1。11多米諾骨牌 有一種多米諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標(biāo)上1至6個(gè)點(diǎn)?，F(xiàn)有一行排列在桌面上：例如，頂行骨牌的點(diǎn)數(shù)之

7、和為6+1+1+1=9；底行骨牌點(diǎn)數(shù)之和為1+5+3+2=11。頂行和底行的差值是2。這個(gè)差值是兩行點(diǎn)數(shù)之和的差的絕對值。每個(gè)多米諾骨牌都可以上下倒置轉(zhuǎn)換，即上部變?yōu)橄虏?，下部變?yōu)樯喜俊，F(xiàn)在的任務(wù)是，以最少的翻轉(zhuǎn)次數(shù)，使得頂行和底行之間的差值最小。12分析以骨牌序列上下兩部分的差值I作為狀態(tài)，把達(dá)到這一狀態(tài)的翻轉(zhuǎn)步數(shù)作為狀態(tài)值，記為f（I）。于是有 f（I）=minf（I+J）+1 （-12=J=12,J為偶數(shù)，且要求當(dāng)前狀態(tài)有差值為J/2的骨牌）。這里，I不是無限增大或減小，其范圍取決于初始骨牌序列的數(shù)字差的和的大小。 13系統(tǒng)可靠性 一個(gè)系統(tǒng)由若干部件串聯(lián)而成，只要有一個(gè)部件故障，系統(tǒng)就不

8、能正常運(yùn)行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動(dòng)進(jìn)入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費(fèi)用也越大，那么在一定總費(fèi)用限制下，系統(tǒng)的最高可靠性等于多少？給定一些系統(tǒng)備用件的單價(jià)Ck，以及當(dāng)用Mk個(gè)此備用件時(shí)部件的正常工作概率Pk（Mk），總費(fèi)用上限C。求系統(tǒng)可能的最高可靠性。 輸入文件格式：第一行：n C第二行：C1 P1(0) P1(1) P1(X1) （0=X1=C/Ck） 第 n 行：Cn Pn(0) Pn(1) Pn(Xn) （0=Xn=C/Cn）14分析例：輸入：2 20 3 0 .6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.

9、7 0.75 0.8 0.8 0.9 0.95 輸出：0.6375設(shè)FI,money表示將money的資金用到前I項(xiàng)備用件中去的最大可靠性，則有 FI,money = maxFI-1 ,moneyk*CostI (0=I=n,0=K= money div Cost(I) )初始： F0,0=0目標(biāo)： Fn,C=015航空旅行給定一張航空圖，圖中的頂點(diǎn)代表城市，邊代表兩城市的直通航線。現(xiàn)要求找出一條滿足下述限制條件的、含城市最多的旅游路線：1.從最西的一個(gè)城市出發(fā)，單方向從西向東途經(jīng)若干城市到達(dá)最東的一個(gè)城市，然后再單方向從東向西飛回起點(diǎn)（可途經(jīng)若干城市）；2.除起點(diǎn)城市外，任何城市只能訪問一次

10、，起點(diǎn)城市被訪問兩次：出發(fā)一次，返回一次。16分析設(shè)fi,j表示頂點(diǎn)i至頂點(diǎn)N與頂點(diǎn)j至頂點(diǎn)N的兩條路線的最多頂點(diǎn)數(shù)，很容易得出，fN,N=1,fi,N=2（當(dāng)該階段中頂點(diǎn)i與頂點(diǎn)N間有直通航線），ai,j=aj,i。這樣，可以得到以下關(guān)系式：fi,j=maxfk,j+1,fi,j (kj且邊(k,i)存在且ak,j0) 時(shí)間復(fù)雜度為O(N3)17積木游戲 有N塊長方體積木，編號依次為1,2,N 。第i塊長寬高分別為ai,bi,ci（i=1,2,N），要從中選出若干塊，將他們摞成M（1= M = N=n），x,y是上面一塊積木接觸面的兩條邊（x=y），則一定滿足m.=x和n=y；下面的積木的編

11、號要小于上面的積木的編號。請你編一程序，尋找一種游戲方案，使得所有能摞成的M根柱子的高度之和最大。18分析設(shè)（1） fi,j,k表示以第i塊積木的第k面為第j根柱子的頂面的最優(yōu)方案的高度總和； （2）blocki,k 記錄每個(gè)積木的三條邊信息（blocki,4:=blocki,1; blocki,5:=blocki,2）。其中blocki,j+2表示當(dāng)把第i塊積木的第j面朝上時(shí)所對應(yīng)的高，即所增加的高度；（3）cani,k,p,kc表示第I塊積木以其第k面朝上，第p塊積木以第kc面朝上時(shí)，能否將積木I放在積木p的上面。1表示能，0表示不能。對于fi,j,k, 有兩種可能： 1. 除去第i塊積木

12、，第j根柱子的最上面的積木為編號為p的，若第p塊積木以第kc面朝上，必須保證當(dāng)?shù)贗塊積木以k面朝上時(shí)能夠被放在上面，即cani,k,p,kc=1； 2. 第i塊積木是第j根柱子的第一塊積木，第j-1根柱子的最上面為第p塊積木，則此時(shí)第p塊積木可以以任意一面朝上。19動(dòng)態(tài)規(guī)劃邊界條件：f1,1,1:=block1,1,3; f1,1,2:=block1,1,4; f1,1,3:=block1,1,5;fi,0,k:=0; (1= i = n, 1= k = 3);時(shí)間復(fù)雜度為O(n2*m) 20石子合并 在一園形操場四周擺放N堆石子(N100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的

13、兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(20),(1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 (2) 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大21示例22貪心法 N=5 石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24總分：62然而仔細(xì)琢磨后，發(fā)現(xiàn)更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次

14、13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24總分：61顯然，貪心法是錯(cuò)誤的。 23動(dòng)態(tài)規(guī)劃 用datai,j表示將從第i顆石子開始的接下來j顆石子合并所得的分值，maxi,j表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)maxi,1 = 0同樣的，我們用mini,j表示將第從第i顆石子開始的接下來j顆石子合并所得的最小值，可以得到類似的方程：mini,j = min(mini, k + mini + k

15、, j k + datai,k + datai+k, j k) (0=k=j)mini,0 = 0這樣，我們完美地解決了這道題。時(shí)間復(fù)雜度也是O(n2)。24多邊形 多角形是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)N個(gè)頂點(diǎn)的多邊形。如圖，這里N=4。每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記，每條邊上有一個(gè)“+”號或“*”號。邊從1編號到N。 第一步，一條邊被拿走；隨后各步包括如下：選擇一條邊E和連接著E的兩個(gè)頂點(diǎn)V1和 V2；得到一個(gè)新的頂點(diǎn)，標(biāo)記為V1與V2通過邊E上的運(yùn)算符運(yùn)算的結(jié)果。最后，游戲中沒有邊，游戲的得分為僅剩余的一個(gè)頂點(diǎn)的值。 25樣例寫一個(gè)程序，對于給定一個(gè)多邊形，計(jì)算出可能的最高得分，并且列出得到這個(gè)

16、分?jǐn)?shù)的過程。26分析 27分析我們先枚舉第一次刪掉的邊，然后再對每種狀態(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求最大值 用f(i,j)表示從j開始，進(jìn)行i次刪邊操作所能得到的最大值，num(i)表示第i個(gè)頂點(diǎn)上的數(shù)，若為加法，那么：28進(jìn)一步分析最后，我們允許頂點(diǎn)上出現(xiàn)負(fù)數(shù)。以前的方程還適不適用呢？這個(gè)例子的最優(yōu)解應(yīng)該是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解將是（-10）*3+2）*（-5）=140。為什么？我們發(fā)現(xiàn)，兩個(gè)負(fù)數(shù)的積為正數(shù)；這兩個(gè)負(fù)數(shù)越小，它們的積越大。我們從前的方程，只是盡量使得局部解最大，而從來沒有想過負(fù)數(shù)的積為正數(shù)這個(gè)問題。 -932-5*圖六+29最終？我們引入函

17、數(shù)fmin和fmax來解決這個(gè)問題。fmax(i,j) 表示從j開始，進(jìn)行i次刪邊操作所能得到的最大值，fmin(i,j) 表示從j開始，進(jìn)行i次刪邊操作所能得到的最小值 。當(dāng)OP=+Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j)30完美解決初始值 Fmax(i,i)=num(i) Fmin(i,i)=num(i)到此為止，整個(gè)問題圓滿解決了。算法的空間復(fù)雜度為O(n2)，算法時(shí)間復(fù)雜度為O(n4)(先要枚舉每一條邊，然后再用復(fù)雜度為O(n3 )的動(dòng)態(tài)規(guī)劃解決）。31Blocks Jimmy最近迷上了一款

18、叫做方塊消除的游戲. 游戲規(guī)則如下：n個(gè)帶顏色方格排成一列，相同顏色的方塊連成一個(gè)區(qū)域（如果兩個(gè)相鄰的方塊顏色相同，則這兩個(gè)方塊屬于同一個(gè)區(qū)域). 游戲時(shí)，你可以任選一個(gè)區(qū)域消去.設(shè)這個(gè)區(qū)域包含的方塊數(shù)為x,則將得到x2的分值.方塊消去之后，右邊的方格將向左移動(dòng).雖然游戲很簡單，但是要得到高分也不是很容易.Jimmy希望你幫助他找出最高可以得到多少分N200.32Sample如圖，依次消去灰,白,黑區(qū)域，你將得到42+32+22=29分，這是最高得分.33算法分析合并顏色序列，如 1 1 1 3 3 2 4 4 4 5 5 根據(jù)方塊消除的規(guī)則，連在一起的相同顏色方塊可以合并 上面的顏色序列為(1,3),(3,2),(2,1),(4,3),(5,2),其中(a,b)表示有b個(gè)顏色為a的連在一起.于是題目可以表示成colori,leni,1=i=m, m表示顏色序列總共有m段. 上面的顏色序列中, m = 5, color1 . 5=(1,3,2,4,5)len 1 . 5=(3,2,1,3,2)34定義狀態(tài)設(shè)S(i,j,k)為(colori,leni),(colori+1,leni+1) (colorj-1,lenj-1)的連續(xù)同色整段以及在一系列消除操作后j后接了k個(gè)顏色為colorj的方塊(colorj,lenj+k)的一個(gè)顏色序列.設(shè)f(i,j,k)表示