最長上升序列

設有整數(shù)序列b1,b2,b3,…,bm，若存在下標i1<i2<i3<…<in，且bi1<bi2<bi3<…<bin，則稱

b1,b2,b3,…,bm中有長度為n的上升序列bi1,

bi2,bi3,…,bin

。求序列b1,b2,b3,…,bm中所有長度(n)最大上升子序列輸入：整數(shù)序列。輸出：最大長度n和所有長度為n的序列個數(shù)。分析設f(i)為前i個數(shù)中的最長上升序列長度

,則f(i)=max{f(j)+1}(1<=j<i<=m,bj<bi)邊界為F(1)=1分析設t(i)為前i個數(shù)中最長序列的個數(shù),則t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j+1))初始為t(i)=1當f(i)=n時，將t(i)累加舉例：

1234658109f:123455677t:111111222答案：f=7時，邊界為∑t=4進一步(3)求本質不同的最長序列個數(shù)有多少個？如：1234658109有，

12346810,12345810,1234689,1234589

都是本質不同的。但對于

1223354f：1223344t：1112244

答案有8個，其中4個1235，4個1234改進算法上例顯然對于相兩個相同的數(shù)，重復算了多次因此，我們對算法進行改進：對原序列按b從小到大（當bi=bj時按F從大到?。┡判颍鲈OOrder(i)記錄新序列中的i個數(shù)在原序列中的位置。可見，求t(i)時，當f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)<Order(i)時，便不累加t(j)。這樣就避免了重復。

上述算法的時間復雜度為O(n2)添括號問題

有一個由數(shù)字1，2，...，9組成的數(shù)字串（長度不超過200），問如何將M(M<=20)個加號("+")插入到這個數(shù)字串中，使所形成的算術表達式的值最小。請編一個程序解決這個問題。注意：加號不能加在數(shù)字串的最前面或最末尾，也不應有兩個或兩個以上的加號相鄰。M保證小于數(shù)字串的長度。例如：數(shù)字串79846，若需要加入兩個加號，則最佳方案為79+8+46，算術表達式的值133。分析考慮到數(shù)據(jù)的規(guī)模超過了長整型,我們注意在解題過程中采用高精度算法.規(guī)劃方程:F[I,J]=MIN{F[I-1,K]+NUM[K+1,J]}(I-1<=K<=J-1)邊界值:F[0,I]:=NUM[1,I] ;F[I，J]表示前J個數(shù)字中添上I個加號后得到的最小值。NUM[I，J]表示數(shù)字串第I位到第J位的數(shù)上述問題的每一步，都只與上一步有關。因此可以采用滾動數(shù)組程序的時間效率約為20*200*200演唱會一場演唱會即將舉行?，F(xiàn)有N（O<N<=200）個歌迷排隊買票，一個人買一張，而售票處規(guī)定，一個人每次最多只能買兩張票。假設第I位歌迷買一張票需要時間Ti（1〈=I〈=n），隊伍中相鄰的兩位歌迷（第j個人和第j+1個人）也可以由其中一個人買兩張票，而另一位就可以不用排隊了，則這兩位歌迷買兩張票的時間變?yōu)镽j，(假如Rj<Tj+Tj+1，則這樣做就可以縮短后面歌迷等待的時間，加快整個售票的進程)?，F(xiàn)給出N，Ti和Ri，求使每個人都買到票的最短時間和方法。分析設f（i）為前i個人花費最短時間于是有

f（i）=min{f（i-1）+Ti，f（i-2）+Ri-1}，初始f（0）=0，f（1）=T1復制書稿假設有M本書（編號為1，2，…M），想將每本復制一份，M本書的頁數(shù)可能不同（分別是P1，P2，…PM）。任務：將這M本書分給K個抄寫員(K<=M)每本書只能分配給一個抄寫員進行抄寫，而每個抄寫員所分配到的書必須是連續(xù)順序的。輸出復制最短時間。復制時間為抄寫頁數(shù)最多的人用去的時間分析設F（I，J）為前I個抄寫員復制前J本書的最小“頁數(shù)最大數(shù)”。于是有

F（I，J）=MIN{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ù)和。起步時F（1，1）=P1。多米諾骨牌有一種多米諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標上1至6個點。現(xiàn)有一行排列在桌面上：例如，頂行骨牌的點數(shù)之和為6+1+1+1=9；底行骨牌點數(shù)之和為1+5+3+2=11。頂行和底行的差值是2。這個差值是兩行點數(shù)之和的差的絕對值。每個多米諾骨牌都可以上下倒置轉換，即上部變?yōu)橄虏?，下部變?yōu)樯喜俊，F(xiàn)在的任務是，以最少的翻轉次數(shù)，使得頂行和底行之間的差值最小。分析以骨牌序列上下兩部分的差值I作為狀態(tài)，把達到這一狀態(tài)的翻轉步數(shù)作為狀態(tài)值，記為f（I）。于是有

f（I）=min{f（I+J）+1}（-12<=J<=12,J為偶數(shù)，且要求當前狀態(tài)有差值為J/2的骨牌）。這里，I不是無限增大或減小，其范圍取決于初始骨牌序列的數(shù)字差的和的大小。系統(tǒng)可靠性

一個系統(tǒng)由若干部件串聯(lián)而成，只要有一個部件故障，系統(tǒng)就不能正常運行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動進入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？給定一些系統(tǒng)備用件的單價Ck，以及當用Mk個此備用件時部件的正常工作概率Pk（Mk），總費用上限C。求系統(tǒng)可能的最高可靠性。

輸入文件格式：第一行：nC第二行：C1P1(0)P1(1)…P1(X1)（0<=X1<=[C/Ck]）

…第n行：CnPn(0)Pn(1)…Pn(Xn)（0<=Xn<=[C/Cn]）分析例：輸入：220 30.60.650.70.750.80.850.950.70.750.80.80.90.95

輸出：0.6375設F[I,money]表示將money的資金用到前I項備用件中去的最大可靠性，則有

F[I,money]=max{F[I-1,money–k*Cost[I]]*p[I,k]}(0<=I<=n,0<=K<=moneydivCost(I))初始：F[0,0]=0目標：F[n,C]=0航空旅行給定一張航空圖，圖中的頂點代表城市，邊代表兩城市的直通航線。現(xiàn)要求找出一條滿足下述限制條件的、含城市最多的旅游路線：1.從最西的一個城市出發(fā)，單方向從西向東途經(jīng)若干城市到達最東的一個城市，然后再單方向從東向西飛回起點（可途經(jīng)若干城市）；2.除起點城市外，任何城市只能訪問一次，起點城市被訪問兩次：出發(fā)一次，返回一次。分析設f[i,j]表示頂點i至頂點N與頂點j至頂點N的兩條路線的最多頂點數(shù)，很容易得出，f[N,N]=1,f[i,N]=2（當該階段中頂點i與頂點N間有直通航線），a[i,j]=a[j,i]。這樣，可以得到以下關系式：f[i,j]=max{f[k,j]+1,f[i,j]}(k<>j且邊(k,i)存在且a[k,j]<>0)時間復雜度為O(N3)f[i,j]=max{f[i,k]+1,f[i,j]}(k<>j且邊(k,I)存在且a[k,j]<>0)積木游戲有N塊長方體積木，編號依次為1,2,…,N。第i塊長寬高分別為ai,bi,ci（i=1,2,…,N），要從中選出若干塊，將他們摞成M（1<=M<=N<=100）根柱子,要求:對于每一根柱子，一定要滿足下面三個條件：除最頂上的一塊積木外，任意一塊積木的上表面同且僅同另一塊積木的下表面接觸；對于任意兩塊上下表面相接觸的積木，若m,n是下面一塊積木接觸面的兩條邊（m>=n），x,y是上面一塊積木接觸面的兩條邊（x>=y），則一定滿足m.>=x和n>=y；下面的積木的編號要小于上面的積木的編號。請你編一程序，尋找一種游戲方案，使得所有能摞成的M根柱子的高度之和最大。分析設（1）f[i,j,k]表示以第i塊積木的第k面為第j根柱子的頂面的最優(yōu)方案的高度總和；（2）block[i,k]記錄每個積木的三條邊信息（block[i,4]:=block[i,1];block[i,5]:=block[i,2]）。其中block[i,j+2]表示當把第i塊積木的第j面朝上時所對應的高，即所增加的高度；（3）can[i,k,p,kc]表示第I塊積木以其第k面朝上，第p塊積木以第kc面朝上時，能否將積木I放在積木p的上面。1表示能，0表示不能。對于f[i,j,k],有兩種可能：

1.除去第i塊積木，第j根柱子的最上面的積木為編號為p的，若第p塊積木以第kc面朝上，必須保證當?shù)贗塊積木以k面朝上時能夠被放在上面，即can[i,k,p,kc]=1；

2.第i塊積木是第j根柱子的第一塊積木，第j-1根柱子的最上面為第p塊積木，則此時第p塊積木可以以任意一面朝上。動態(tài)規(guī)劃邊界條件：f[1,1,1]:=block[1,1,3];f[1,1,2]:=block[1,1,4];f[1,1,3]:=block[1,1,5];f[i,0,k]:=0;(1<=i<=n,1<=k<=3);時間復雜度為O(n2*m)石子合并在一園形操場四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(≤20), (1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少(2)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大示例貪心法N=5石子數(shù)分別為346542。用貪心法的合并過程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24總分：62然而仔細琢磨后，發(fā)現(xiàn)更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24總分：61顯然，貪心法是錯誤的。動態(tài)規(guī)劃用data[i,j]表示將從第i顆石子開始的接下來j顆石子合并所得的分值，max[i,j]表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2<=k<=j)max[i,1]=0同樣的，我們用min[i,j]表示將第從第i顆石子開始的接下來j顆石子合并所得的最小值，可以得到類似的方程：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0<=k<=j)min[i,0]=0這樣，我們完美地解決了這道題。時間復雜度也是O(n2)。多邊形

多角形是一個單人玩的游戲，開始時有一個N個頂點的多邊形。如圖，這里N=4。每個頂點有一個整數(shù)標記，每條邊上有一個“+”號或“*”號。邊從1編號到N。第一步，一條邊被拿走；隨后各步包括如下：選擇一條邊E和連接著E的兩個頂點V1和V2；得到一個新的頂點，標記為V1與V2通過邊E上的運算符運算的結果。最后，游戲中沒有邊，游戲的得分為僅剩余的一個頂點的值。樣例寫一個程序，對于給定一個多邊形，計算出可能的最高得分，并且列出得到這個分數(shù)的過程。分析

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

Fmax(i,i)=num(i)Fmin(i,i)=num(i)到此為止，整個問題圓滿解決了。算法的空間復雜度為O(n2)，算法時間復雜度為O(n4)(先要枚舉每一條邊，然后再用復雜度為O(n3)的動態(tài)規(guī)劃解決）。BlocksJimmy最近迷上了一款叫做方塊消除的游戲.游戲規(guī)則如下：n個帶顏色方格排成一列，相同顏色的方塊連成一個區(qū)域（如果兩個相鄰的方塊顏色相同，則這兩個方塊屬于同一個區(qū)域).游戲時，你可以任選一個區(qū)域消去.設這個區(qū)域包含的方塊數(shù)為x,則將得到x2的分值.方塊消去之后，右邊的方格將向左移動.雖然游戲很簡單，但是要得到高分也不是很容易.Jimmy希望你幫助他找出最高可以得到多少分N<200.Sample如圖，依次消去灰,白,黑區(qū)域，你將得到42+32+22=29分，這是最高得分.

算法分析合并顏色序列，如

11133244455

根據(jù)方塊消除的