動態(tài)規(guī)劃經典題(C版)

第九章動態(tài)規(guī)劃第一節(jié)動態(tài)規(guī)劃的基本模型第二節(jié)動態(tài)規(guī)劃與遞推第三節(jié)背包問題第四節(jié)動態(tài)規(guī)劃經典題

動態(tài)規(guī)劃程序設計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態(tài)規(guī)劃程序設計往往是針對一種最優(yōu)化問題，由于各種問題的性質不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論，逐漸學會并掌握這一設計方法。第四節(jié)動態(tài)規(guī)劃經典題【例9-18】、合并石子【問題描述】在一個操場上一排地擺放著Ｎ堆石子。現要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的２堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分?！揪幊倘蝿铡吭囋O計一個程序，計算出將Ｎ堆石子合并成一堆的最小得分?！据斎敫袷健康谝恍袨橐粋€正整數N(2≤Ｎ≤100)；以下Ｎ行,每行一個正整數，小于10000，分別表示第i堆石子的個數(1≤i≤N)?！据敵龈袷健繛橐粋€正整數，即最小得分。s[i]表示前i堆石頭的價值總和，f[i][j]表示把第i堆到第j堆的石頭合并成一堆的最優(yōu)值。

for(i=n-1;i>=1;i--)for(j=i+1;j<=n;j++)for(k=i;k<=j-1;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);輸出f[1][n]【輸入樣例】713781621418【輸出樣例】239【參考程序】#include<cstdio>#include<cstring>intmin(inta,intb){returna>b?b:a;//三目運算符，相當于if(a>b)returnb;elsereturna;}intf[101][101];ints[101];intn,i,j,k,x;intmain(){scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);s[i]=s[i-1]+x;}memset(f,127/3,sizeof(f));//賦值127是很大的正數，若無/3后面的相加

for(i=1;i<=n;i++)f[i][i]=0;//可能超出int的范圍

for(i=n-1;i>=1;i--)for(j=i+1;j<=n;j++)for(k=i;k<=j-1;k++)

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);

printf("%d\n",f[1][n]);return0;}【例9-19】乘積最大【問題描述】

今年是國際數學聯盟確定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數學智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：設有一個長度為N的數字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積最大。同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：有一個數字串：312，當N=3，K=1時會有以下兩種分法：1）3*12=362）31*2=62

這時，符合題目要求的結果是：31*2=62。現在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案?！据斎敫袷健縨ul.in

第一行共有2個自然數N，K（6≤N≤40，1≤K≤6）第二行是一個長度為N的數字串?！据敵龈袷健縨ul.out

輸出所求得的最大乘積（一個自然數）。【輸入樣例】421231【輸出樣例】62【算法分析】

此題滿足動態(tài)規(guī)劃法的求解標準，我們把它按插入的乘號數來劃分階段，若插入K個乘號，可把問題看做是K個階段的決策問題。設f[i][k]表示在前i位數中插入K個乘號所得的最大值，a[j][i]表示從第j位到第i位所組成的自然數。用f[i][k]存儲階段K的每一個狀態(tài)，可以得狀態(tài)轉移方程：

f[i][k]=max{f[j][k-1]*a[j+1][i]}（k<=j<=i）邊界值：

f[j][0]=a[1][j](1<j<=i)根據狀態(tài)轉移方程，我們就很容易寫出動態(tài)規(guī)劃程序：for(k=1;k<=r;k++)//r為乘號個數

for(i=k+1;i<=n;i++)for(j=k;j<i;j++)if(f[i][k]<f[j][k-1]*a[j+1][i])f[i][k]=f[j][k-1]*a[j+1][i]【參考程序】#include<cstdio>longlonga[11][11],f[11][11];longlongs;intn,i,k,k1,j;intmax(inta,intb){returna>b?a:b;}intmain(){scanf("%d%d",&n,&k1);scanf("%lld",&s);for(i=n;i>=1;i--){a[i][i]=s%10;s/=10;

}for(i=2;i<=n;i++)for(j=i-1;j>=1;j--)a[j][i]=a[j][i-1]*10+a[i][i];

for(i=1;i<=n;i++)//預處理不加乘號的情況

f[i][0]=a[1][i];for(k=1;k<=k1;k++)for(i=k+1;i<=n;i++)for(j=k;j<i;j++)

f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);

printf("%lld\n",f[n][k1]);

return0;}【例9-20】編輯距離【問題描述】設A和B是兩個字符串。我們要用最少的字符操作次數，將字符串A轉換為字符串B。這里所說的字符操作共有三種：1、刪除一個字符；2、插入一個字符；3、將一個字符改為另一個字符。【編程任務】對任的兩個字符串A和B，計算出將字符串A變換為字符串B所用的最少字符操作次數?！据斎敫袷健縠dit.in第一行為字符串A；第二行為字符串B；字符串A和B的長度均小于200。【輸出格式】edit.out只有一個正整數，為最少字符操作次數?！据斎霕永縮fdqxbwgfdgw【輸出樣例】4【算法分析】狀態(tài)：f[i][j]記錄ai與bj的最優(yōu)編輯距離結果：f[m][n]，其中m、n分別是a、b的串長初值：b串空，要刪a串長個字符；a串空，要插b串長個字符轉移方程：當a[i]=b[j]時，f[i][j]=f[i-1][j-1]，否則，

f[i][j]=min(f[i-1][j-1]+1,f[i][j-1]+1,f[i-1][j]+1)說明：f[i-1][j-1]+1：改a[i]為b[j]；

f[i][j-1]+1：a[i]后插入b[j-1]；

f[i-1][j]+1：刪a[i]?！緟⒖汲绦颉?include<cstdio>#include<cstring>intmin(inta,intb){returna<b?a:b;}intf[202][202];chars1[202],s2[202];inti,j,k,m,n;intmain(){scanf("%s%s",s1,s2);m=strlen(s1);n=strlen(s2);for(i=1;i<=m;i++)f[i][0]=i;//到i位置為止把字符串A的內容全部刪除

for(i=1;i<=n;i++)f[0][i]=i;//在開頭給字符串A添上和B到i位置相同的字符

for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1];elsef[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;

printf("%d\n",f[m][n]);return0;}【例9-21】方格取數【問題描述】

設有N×N的方格圖，我們在其中的某些方格中填入正整數，而其它的方格中則放入數字0。如下圖所示：某人從圖中的左上角的A出發(fā)，可以向下行走，也可以向右行走，直到達右下角的B點。在走過的路上，他可以取走方格中的數(取走后的方格中將變?yōu)閿底?)?！揪幊倘蝿铡看巳藦腁點到B點共走了兩次，試找出兩條這樣的路徑，使得取得的數字和為最大?！据斎敫袷健縋ane.in輸入文件Pane.in第一行為一個整數N（N≤10），表示N×N的方格圖。接下來的每行有三個整數，第一個為行號數，第二個為列號數，第三個為在該行、該列上所放的數。一行000表示結束?！据敵龈袷健縋ane.out輸出文件Pane.out包含一個整數，表示兩條路徑上取得的最大的和。【輸入樣例】

823132663574414522156463157214000【輸出樣例】67【算法分析】一個四重循環(huán)枚舉兩條路分別走到的位置。由于每個點均從上或左繼承而來，故內部有四個if，分別表示兩個點從上上、上左、左上、左左繼承來時，加上當前兩個點所取得的最大值。a[i][j]表示(i,j)格上的值，sum[i][j][h][k]表示第一條路走到(i,j)，第二條路走到(h,k)時的最優(yōu)解。例如，sum[i][j][h][k]=max{sum[i][j][h][k],sum[i-1][j][h-1][k]+a[i][j]+a[h][k]}，表示兩點均從上面位置走來。當(i,j)<>(h,k)）時sum[i][j][h][k]:=max{sum[i-1][j][h-1][k],sum[i][j-1][h][k-1],sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]}+a[i][j]+a[h][k];當(i,j)=(h,k)時sum[i][j][h][k]:=max{sum[i-1][j][h-1][k],sum[i][j-1][h][k-1],sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]}+a[i][j];【參考程序1】#include<cstdio>intmax(inta,intb){returna>b?a:b;}inta[51][51];intsum[51][51][51][51];intn,i,j,h,k,x,y,z;intmain(){scanf("%d%d%d%d",&n,&x,&y,&z);while(x&&y&&z)//C++中大于0的正整數都看作true，只有0看作false{a[x][y]=z;

scanf("%d%d%d",&x,&y,&z);}for(i=1;i<=n;i++)

for(j=1;j<=n;j++)for(h=1;h<=n;h++)for(k=1;k<=n;k++){inttmp1=max(sum[i-1][j][h-1][k],sum[i][j-1][h][k-1]);inttmp2=max(sum[i-1][j][h][k-1],sum[i][j-1][h-1][k]);

sum[i][j][h][k]=max(tmp1,tmp2)+a[i][j];if(i!=h&&j!=k)sum[i][j][h][k]+=a[h][k];}printf("%d\n",sum[n][n][n][n]);

return0;}【例9-22】低價購買(buylow)【問題描述】“低價購買”這條建議是在股票市場取得成功的一半規(guī)則。要想被認為是偉大的投資者，你必須遵循以下的購買建議:“低價購買；再低價購買”。每次你購買一支股票,你必須用低于你上次購買它的價格購買它。買的次數越多越好!你的目標是在遵循以上建議的前提下，求你最多能購買股票的次數。你將被給出一段時間內一支股票每天的出售價(216范圍內的正整數)，你可以選擇在哪些天購買這支股票。每次購買都必須遵循“低價購買；再低價購買”的原則。寫一個程序計算最大購買次數。這里是某支股票的價格清單：日期123456789101112價格686954646864706778629887最優(yōu)秀的投資者可以購買最多4次股票，可行方案中的一種是：日期25610價格69686462【輸入格式】輸入文件共兩行，第1行:N(1<=N<=5000)，股票發(fā)行天數；第2行:N個數，是每天的股票價格?！据敵龈袷健枯敵鑫募H一行，包含兩個數:最大購買次數和擁有最大購買次數的方案數(<=231)，當兩種方案“看起來一樣”時（就是說它們構成的價格隊列一樣的時候）,這2種方案被認為是相同的?！据斎霕永縝uylow.in12696854706864706778629887【輸出樣例】buylow.out44【算法分析1】先探索一下樣例，最大購買次數為4次，共有4種方案，分別為69、68、64、62；69、68、67、62；70、68、64、62；70、68、67、62。我們發(fā)現，這道題實際上是在一個數列中選出一個序列，使得這個序列是一個下降序列（即序列中的任意一個數必須大于它后面的任何一個數），且要使這個序列的長度最長。但是這道題要輸出總的方案數，這就需要對原有的求解過程做一些變動。求方案總數最主要的是要剔除重復方案。在樣例中，第2和第5個數都是68。以第一個68結尾的最長下降序列的方案為69、68；以第二個68結尾的最長下降序列的方案為69、68和70、68——這時候就產生了方案的重復，即產生了兩個69、68。顯然后面的68要比前面一個更優(yōu)，因為后面的68位置更靠后，以這個68結尾的最長下降序列的總數肯定要比前面一個多，而且其方案必定囊括了前面一個68的所有方案。因此，在解題過程中，我們就可以只考慮后面一個68。推廣開來，如果當前狀態(tài)之前存在重復的狀態(tài)，我們只要考慮離當前狀態(tài)位置最近的那一個即可。設F（i）表示到第i天，能夠購買的最大次數，顯然有：F（1）=1，F（i）=max{F(j)+1}(1<=j<=i-1,且OK[j]=true)，OK[j]=true表示相同價格時，該位置更優(yōu)。【參考程序1】#include<cstdio>#include<cstring>boolok[50001];inta[5001],b[5001],f[5001];intn,i,j,k,max,num;intmain(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);

b[1]=1;f[1]=1;for(i=2;i<=n+1;i++){max=0;f[i]=1;for(j=i-1;j>=1;j--)if(a[i]<a[j])if(b[j]>max)//b[j]表示以第j天結尾的最大購買次數{max=b[j];memset(ok,1,sizeof(ok));

ok[a[j]]=false;f[i]=f[j];

}elseif(b[j]==max&&ok[a[j]])

{ok[a[j]]=false;f[i]+=f[j];

}b[i]=max+1;}printf("%d%d",b[n+1]-1,f[n+1]);return0;}【算法分析2】關于求第一問，很簡單，求最長下降序列就行了，依次求出以第i個元素為最后一個元素時的最長下降序列的長度longest(i)，邊界條件longest(1)=1，狀態(tài)轉移方程為：longest(i)=max{longest(j)+1},其中i>1，j=1,2…,i-1，且j同時要滿足條件：序列中第j個元素大于第i個元素。關于第二問，就并非如此簡單了，因為需要求出最大購買次數的方案數，并且方案“看起來”不能重復，即，購買價格序列是不能一樣的。如何解決該問題，我們來看一個簡單的例子，假如股票價格序列為:4、2、2、3、1，則購買方案有兩種4、2、1和4、3、1其中4、2、1序列重復了，我們在求longest(i)時，longest(1)=1，longest(2)=2，longest(3)=2，longest(4)=2，那么我們求longest(5)時到底選用前邊的那一組數據呢？顯然，那一組都可以，這就使總方案數不唯一了，我們需要記錄下來此時的方案數solution(5)，由于股價p(2)和p(3)相同，所以solution(2)和solution(3)只能有一個累加到solution(5)里，我們取solution值較大的累加到solution(5)里，如果solution(2)=solution(3)，則選solution(2)，所以solution(5)=solution(2)+solution(4)，由此我們可以寫出狀態(tài)轉移方程:solution(i)=∑solution(j)，其中j滿足：0<j<i，且longest(j)=longest(i)-1,且p(j)值不重復。為了便于計算，我們這里把i的取值擴大到n+1，p[n+1]=-1，我們要求的longest值即為longest[n+1]-1，solution值即為solution[n+1]，想一想這樣處理有什么好處？為什么？【參考程序2】#include<cstdio>#include<cstring>constintmaxn=5002;structprice{intlongest,solution;}d[maxn];intp[maxn],t[maxn][2];intn,i,j,k,maxlong;intmain(){scanf("%d",&n);

for(i=1;i<=n;i++)scanf("%d",&p[i]);

p[n+1]=-1;d[1].longest=d[1].solution=1;

for(i=2;i<=n+1;i++){maxlong=0;for(j=1;j<i;j++)if(p[j]>p[i]&&d[j].longest>maxlong)maxlong=d[j].longest;d[i].longest=maxlong+1;d[i].solution=0;memset(t,0,sizeof(t));if(!maxlong)d[i].solution=1;else/*當d[j].longest等于d[i].longest-1，即等于maxlong，且p[j]>p[i]時，求出d[j].solution值并累加得到d[i].solution，其中股價相等時，取d[j].solution值大的累加入d[i].solution*/for(j=1;j<i;j++)if(d[j].longest==maxlong&&p[j]>p[i])

{k=1;while(t[k][0]!=p[j]&&t[k][0]!=0)k++;if(!t[k][0])/*當股價不相等時，直接累加入d[i].solution，并增加數組k的記錄*/

{t[k][0]=p[j];t[k][1]=d[j].solution;d[i].solution+=d[j].solution;}else/*當股價有相等且d[j].solution值較大時，將兩天的solution差值累加入d[i].solution，以達到取較大值累加的目的，并修改數組k的相應得記錄*/

{if(t[k][1]<d[j].solution)

d[i].solution+=d[j].solution-t[k][1];t[k][1]=d[j].solution;}}}printf("%d%d\n",d[n+1].longest-1,d[n+1].solution);

return0;}【例9-23】最長公共子序列【問題描述】一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=<x1,x2,…,xm>，則另一序列Z＝<z1，z2，…，zk>是X的子序列是指存在一個嚴格遞增的下標序列<i1,i2,…,ik>,使得對于所有j=1,2,…,k有：

Xij=Zj例如，序列z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相應的遞增下標序列為<2,3,5,7>。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱z是序列x和Y的公共子序列。例如，若x＝<A,B,C,B,D,A,B>和Y＝<B,D,C,A,B,A>，則序列<B,C,A>是X和Y的一個公共子序列,序列<B,C,B,A>也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列．因為x和Y沒有長度大于4的公共子序列。給定兩個序列X＝<x1，x2，…，xm>和Y=<y1,y2…．yn>．要求找出X和Y的一個最長公共子序列。【輸入格式】輸入文件共有兩行。每行為一個由大寫字母構成的長度不超過200的字符串，表示序列X和Y?！据敵龈袷健枯敵鑫募谝恍袨橐粋€非負整數。表示所求得的最長公共子序列的長度。若不存在公共子序列．則輸出文件僅有一行輸出一個整數0。否則在輸出文件的第二行輸出所求得的最長公共子序列(也用一個大寫字母組成的字符串表示)。若符合條件的最長公共子序列不止一個，只需輸出其中任意的一個?！緲永斎搿縇CS.INABCBDABBDCABA【樣例輸出】LCS.OUT4BCBA【問題分析】動態(tài)規(guī)劃算法可有效地解此問題。下面我們按照動態(tài)規(guī)劃算法設計的各個步驟來設計一個解此問題的有效算法。1．最長公共子序列的結構解最長公共子序列問題時最容易想到的算法是窮舉搜索法。即對X的每一個子序列。檢查它是否也是Y的子序列。從而確定它是否為X和Y的公共子序列。并且在檢查過程中選出最長的公共子序列。X的所有子序列都檢查過后即可求出X和Y的最長公共子序列，X的一個子序列相應于下標序列｛1，2，…，m｝的一個子序列。因此，X共有2^m個不同子序列，從而窮舉搜索法需要指數時間。事實上，最長公共子序列問題也有最優(yōu)子結構性質，因為我們有如下定理：定理：LCS的最優(yōu)子結構性質設序列X=<x1,x2,…，xm>和Y=<y1,y2,…，yn>的一個最長公共子序列Z=<z1,z2,…,zk>．則：若xm=yn則zk=xm=yn且Zk-1是Xm-1和Yn-1最長公共子序列：若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列；若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。其中Xm-1=<x1,x2，…,xm-1>．Yn-1=<y1,y2,…,yn-1>．Zk-1=<z1,z2,…，Zk-1>。證明：用反證法。若zk≠xm且xm=yn,則<z1,z2,….zk,xm>是X和Y的長度為k+1的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾，因此，必有zk=xm=yn，由此可知Zk-1是Xm-1和Yn-1的一個長度為k－1的公共子序列。若Xm-1和Yn-1有一個長度大于k-1的公共子序列W,則將xm加在其尾部將產生X和Y的一個長度大于k的公共子序列．此為矛盾。故Zk-1是Xm-1和Yn-1的一個最長公共子序列。由于zk≠xm,Z是Xm-1和Y的一個公共子序列：若Xm-1和Y有一個長度大于k的公共子序列W,則W也是X和Y的一個長度大于k的公共子序列。這與Z是X和Y的一個最長公共子序列矛盾。由此即知Z是Xm-1和Y的一個最長公共子序列。這個定理告訴我們，兩個序列的最長公共子序列包含了這兩個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結構性質。2．子問題重疊性質由最長公共子序列問題的最優(yōu)子結構性質可知．要找出X＝<x1，x2．…,xm>和Y＝<y1，y2，…，yn>的最長公共子序列．可按以下方式遞歸地進行：當xm=yn時．找出xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm≠yn時，必須解兩個子問題．即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質，例如．在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題．即計算Xm-1和Yn-1的最長公共子序列。我們來建立子問題的最優(yōu)值的遞歸關系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。當i=0或j=0時,空序列是Xi和Yj的最長公共子序列，故c[i][j]=0。由定理可建立遞歸關系如下：3．計算最優(yōu)值直接利用上式容易寫出一個計算c[i][j]的遞歸算法．但其計算時間是隨輸入長度指數增長的。由于在所考慮的子問題空間中，總共只有O(m*n)個不同的子問題．因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1，x2，…,xm>和Y=<y1,y2,…,yn>作為輸入。輸出兩個數組c[0..m][0..n]和b[1..m][1..n]。其中c[i][j]存儲Xi與Yj的最長公共子序列的長度,b[i][j]記錄指示c[i][j]的值是由哪一個子問題的解達到的．這在構造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于c[m][n]中。由于每個數組單元的計算耗時O(1)，算法LCS_LENGTH耗時O(mn)。4．構造最長公共子序列由算法LCSENGTH計算得到的數組b可用于快速構造序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最長公共子序列。首先從b[m][n]開始，沿著其中的箭頭所指的方向在數組b中搜索。當b[i][j]中遇到“↖”時，表示Xi與Yj的最長公共子序列是由Xi-1與Yj-1的最長公共子序列在尾部加上xi得到的子序列；當b[i][j]中遇到“↑”時．表示Xi與Yj的最長公共子序列和Xi-1與Yj的最長公共子序列相同；當b[i][j]中遇到“←”時,表示Xi與Yj的最長公共子序列和Xi與Yj-1的最長公共子序列相同。在本算法中，每一次的遞歸調用使i或j減1，因此算法的計算時間為O(m+n)?！緟⒖汲绦颉?/ex9_23#include<cstdio>#include<cstring>#include<string>usingnamespacestd;intmax(inta,intb){returna>b?a:b;}constintmaxlen=201;intc[maxlen][maxlen];intn,i,j,l1,l2;charx[maxlen],y[maxlen];stringz="";intmain(){scanf("%s%s",x,y);

l1=strlen(x);l2=strlen(y);

for(i=1;i<=l1;i++)for(j=1;j<=l2;j++)

if(x[i-1]==y[j-1])c[i][j]=c[i-1][j-1]+1;elsec[i][j]=max(c[i-1][j],c[i][j-1]);

printf("%d\n",c[l1][l2]);i=l1;j=l2;

while(i&&j)if(x[i-1]==y[j-1]){z=x[--i]+z;//string類重載了運算符“+”、“=”，可直接使用

j--;}elseif(c[i-1][j]>c[i][j-1])i--;elsej--;printf("%s\n",z.c_str());//string類應加.c_str()獲得相應的字符串值

return0;}【例9-24】復制書稿(book.pas)【問題描述】

現在要把m本有順序的書分給k個人復制（抄寫），每一個人的抄寫速度都一樣，一本書不允許給兩個（或以上）的人抄寫，分給每一個人的書，必須是連續(xù)的，比如不能把第一、第三和第四本書給同一個人抄寫?，F在請你設計一種方案，使得復制時間最短。復制時間為抄寫頁數最多的人用去的時間?！据斎敫袷健?/p>

第一行兩個整數m，k；（k≤m≤500）第二行m個整數，第i個整數表示第i本書的頁數?！据敵龈袷健?/p>

共k行，每行兩個整數，第i行表示第i個人抄寫的書的起始編號和終止編號。k行的起始編號應該從小到大排列，如果有多解，則盡可能讓前面的人少抄寫?！据斎胼敵鰳永縝ook.in book.out93 67 89【問題分析】

本題可以用動態(tài)規(guī)劃解決，設f(k,m)為前m本書交由k個人抄寫，需要的最短時間，則狀態(tài)轉移方程為

f[k][m]=min{max{f[k-1][i],},i=1,2,…,m-1}

動態(tài)規(guī)劃求出的僅僅是最優(yōu)值，如果要輸出具體方案，還需根據動態(tài)規(guī)劃計算得到的最優(yōu)值，做一個貪心設計。具體來說，設最優(yōu)值為T，那么k個人，每個人抄寫最多T頁。從最后一本書開始按逆序將書分配給k人去抄寫，從第k個人開始，如果他還能寫，就給他；否則第k個人工作分配完畢，開始分配第k-1個人的工作；以后再是第k-2個、第k-3個、……直至第1個。一遍貪心結束后，具體的分配方案也就出來了。【參考程序】#include<iostream>#include<cstdio>#include<cstdlib>usingnamespacestd;intmax1(int,int);intprint(int,int);intx,y,i,j,m,n,k,t,l;inta[501],f[501][501],d[501];intmain(){cin>>m>>k;for(i=0;i<=500;i++)for(j=0;j<=500;j++)f[i][j]=10000000;for(j=1;j<=m;j++){cin>>a[j];//輸入m本書的頁數

d[j]=d[j-1]+a[j];//d[j]為前j本書總的頁數

f[1][j]=d[j];//f[i][j]為一個人抄前j本書所需時間

}for(i=2;i<=k;i++)//f[k][m]為前m本書交由k個人抄寫，需要的最短時間

for(j=1;j<=m;j++)

for(l=1;l<=j-1;l++)if(max1(f[i-1][l],d[j]-d[l])<f[i][j])f[i][j]=max1(f[i-1][l],d[j]-d[l]);}print(m,k);//從第k個開始分配抄寫方案intmax1(intx,inty)//求x和y中最大值{if(x>y)returnx;elsereturny;}intprint(inti,intj)//遞歸輸出抄寫頁數的方案{intt,x;if(j==0)return0;if(j==1)//第1個人抄寫1到i本書

{cout<<1<<""<<i<<endl;return0;}t=i;x=a[i];while(x+a[t-1]<=f[k][m])//從最后一本書按逆序分配第j個人抄寫，只要能寫，就給他

{x+=a[t-1];t--;}print(t-1,j-1);//用遞歸過程給第j-1個人分配抄寫方案，這時只有t-1書了

cout<<t<<""<<i<<endl;//遞歸返回時輸出，因為遞歸過程是最后1個人先分配抄書}【例題9-25】櫥窗布置（Flower）【問題描述】

假設以最美觀的方式布置花店的櫥窗，有F束花，每束花的品種都不一樣，同時，至少有同樣數量的花瓶，被按順序擺成一行，花瓶的位置是固定的，并從左到右，從1到V順序編號，V是花瓶的數目，編號為1的花瓶在最左邊，編號為V的花瓶在最右邊，花束可以移動，并且每束花用1到F的整數惟一標識，標識花束的整數決定了花束在花瓶中列的順序即如果I<J，則花束I必須放在花束J左邊的花瓶中。例如，假設杜鵑花的標識數為1，秋海棠的標識數為2，康乃馨的標識數為3，所有的花束在放人花瓶時必須保持其標識數的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數目大于花束的數目，則多余的花瓶必須空，即每個花瓶中只能放一束花。每一個花瓶的形狀和顏色也不相同，因此，當各個花瓶中放人不同的花束時會產生不同的美學效果，并以美學值(一個整數)來表示，空置花瓶的美學值為0。在上述例子中，花瓶與花束的不同搭配所具有的美學值，可以用如下表格表示。根據表格，杜鵑花放在花瓶2中，會顯得非常好看，但若放在花瓶4中則顯得很難看。為取得最佳美學效果，必須在保持花束順序的前提下，使花的擺放取得最大的美學值，如果具有最大美學值的擺放方式不止一種，則輸出任何一種方案即可。題中數據滿足下面條件：1≤F≤100，F≤V≤100，－50≤AIJ≤50，其中Aij是花束I擺放在花瓶J中的美學值。輸入整數F，V和矩陣(AIJ)，輸出最大美學值和每束花擺放在各個花瓶中的花瓶編號。┌───┬───┬───┬───┬───┬───┐

│

│花瓶1│花瓶2

│花瓶3│花瓶4

│花瓶5│

├───┼───┼───┼───┼───┼───┤

│杜鵑花│

7

│

23

│

-5

│

-24

│

16

│

├───┼───┼───┼───┼───┼───┤

│秋海棠│

5

│

21

│

-4

│

10

│

23

│

├───┼───┼───┼───┼───┼───┤

│康乃馨│

-21

│

5

│

-4

│

-20

│

20

│

└───┴───┴───┴───┴───┴───┘1、假設條件

1≤F≤100，其中F為花束的數量，花束編號從1至F。

F≤V≤100，其中V是花瓶的數量。

-50≤Aij≤50，其中Aij是花束i在花瓶j中的美學值。2、輸入輸入文件是flower.in。第一行包含兩個數：F，V。隨后的F行中，每行包含V個整數，Aij

即為輸入文件中第（i+1）行中的第j個數。3、輸出輸出文件必須是名為flower.out的正文文件，文件應包含兩行：第一行是程序所產生擺放方式的美學值。第二行必須用F個數表示擺放方式，即該行的第K個數表示花束K所在的花瓶的編號。【樣例輸入】35723–5–2416521-41023-215-4-2020【樣例輸出】53245【解法一】【算法分析】

問題實際就是給定F束花和V個花瓶，以及各束花放到不同花瓶中的美學值，要求你找出一種擺放的方案，使得在滿足編號小的花放進編號小的花瓶中的條件下，美學值達到最大。將問題進行轉化，找出問題的原型。首先，看一下上述題目的樣例數據表格。將擺放方案的要求用表格表現出來，則擺放方案需要滿足：每行選且只選一個數(花瓶)；擺放方案的相鄰兩行中，下面一行的花瓶編號要大于上面一行的花瓶編號兩個條件。這時可將問題轉化為：給定一個數字表格，要求編程計算從頂行至底行的一條路徑，使得這條路徑所經過的數字總和最大(要求每行選且僅選一個數字)。同時，路徑中相鄰兩行的數字，必須保證下一行數字的列數大于上一行數字的列數?？吹浇涍^轉化后的問題，發(fā)現問題與“數學三角形”問題十分相似，數字三角形問題的題意是：給定一個數字三角形，要求編程計算從頂至底的一條路徑，使得路徑所經過的數字總和最大(要求每行選且僅選一個數字)。同時，路徑中相鄰兩行的數字，必須保證下一行數字的列數與上一行數字的列數相等或者等于上一行數字的列數加1。上例中已經知道：數字三角形中的經過數字之和最大的最佳路徑，路徑的每個中間點到最底層的路徑必然也是最優(yōu)的，可以用動態(tài)規(guī)劃方法求解，對于“花店櫥窗布置”問題經過轉化后，也可采取同樣的方法得出本題同樣符合最優(yōu)性原理。因此，可以對此題采用動態(tài)規(guī)劃的方法。【參考程序】#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){inta[101][101],b[101][101],c[101][101],d[101];//a[i][j]花束i放在花瓶j中的美學值

//b[i][j]前i束花放在前j個花瓶中的最優(yōu)解

//c[i][j]在b[i][j]的最優(yōu)解中，花束i-1的位置

intf,v,i,j,k,max;//f,v花束和花瓶的數目

cin>>f>>v;for(i=1;i<=f;i++)

for(j=1;j<=v;j++)cin>>a[i][j];memset(b,128,sizeof(b));//這樣處理，可以保證每束花都放進花瓶

for(i=1;i<=v-f+1;i++)//初始化第1束花放在第i個花瓶的情況

b[1][i]=a[1][i];for(i=2;i<=f;i++)for(j=i;j<=v-f+i;j++)for(k=i-1;k<=j-1;k++)//枚舉花束i-1的位置

if(b[i-1][k]+a[i][j]>b[i][j]){b[i][j]=b[i-1][k]+a[i][j];//更新當前最優(yōu)解

c[i][j]=k;//前一個花束的位置為k}max=-2100000000;for(i=f;i<=v;i++)if(b[f][i]>max){max=b[f][i];//選擇全局最優(yōu)解

k=i;//k最后一束花的位置

}cout<<max<<endl;//打印最優(yōu)解

for(i=1;i<=f;i++){d[i]=k;k=c[f-i+1][k];}for(i=f;i>=2;i--)

cout<<d[i]<<"";

cout<<d[1]<<endl;}

由此可看出，對于看似復雜的問題，通過轉化就可變成簡單的經典的動態(tài)規(guī)劃問題。在問題原型的基礎上，通過分析新問題與原問題的不同之處，修改狀態(tài)轉移方程，改變問題狀態(tài)的描述和表示方式，就會降低問題規(guī)劃和實現的難度，提高算法的效率。由此可見，動態(tài)規(guī)劃問題中具體的規(guī)劃方法將直接決定解決問題的難易程度和算法的時間與空間效率，而注意在具體的規(guī)劃過程中的靈活性和技巧性將是動態(tài)規(guī)劃方法提出的更高要求?！窘夥ǘ俊舅惴ǚ治觥縡lower一題是IOI99第一天第一題，該題如用組合的方法處理，將會造成超時。正確的方法是用動態(tài)規(guī)劃，考慮角度為一束一束地增加花束，假設用b[i][j]表示1～i束花放在1到j之間的花瓶中的最大美學值，其中i<=j，則b[i][j]=max(b[i-1][k-1]+A[i][k])，其中i<=k<=j，A[i][k]的含義參見題目。輸出結果時，顯然使得b[F][k]取得總的最大美觀值的第一個k值就是第F束花應該擺放的花瓶位置，將總的最大美觀值減去A[i][k]的值即得到前k-1束花放在前k-1個瓶中的最大美觀值，依次使用同樣的方法就可求出每一束花應該擺放的花瓶號。由于這一過程是倒推出來的，所以程序中用遞歸程序來實現。【參考程序】#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;voidprint(int,int);intmax(inta,intb){returna>b?a:b;}inta[101][101],b[101][101];intmain(){intf,v;cin>>f>>v;for(inti=1;i<=f;i++)for(intj=1;j<=v;j++)cin>>a[i][j];memset(b,128,sizeof(b));//初始化b數組

for(inti=0;i<101;i++)b[0][i]=0;//沒有放花時，美學值為0。這也是初始化

for(inti=1;i<=f;i++)for(intj=i;j<=v-f+i;j++){for(intk=i;k<=j;k++)

b[i][j]=max(b[i][j],b[i-1][k-1]+a[i][k]);

}intc=-1000000;for(inti=f;i<=v;i++)if(b[f][i]>c)c=b[f][i];

cout<<c<<endl;print(f,c);}voidprint(inti,intj){intn;if(i>0){n=i;while(b[i][n]!=j){n++;}print(i-1,j-a[i][n]);cout<<n<<"";}}記憶化搜索的應用一般來說，動態(tài)規(guī)劃總要遍歷所有的狀態(tài)，而搜索可以排除一些無效狀態(tài)。更重要的是搜索還可以剪枝，可能剪去大量不必要的狀態(tài)，因此在空間開銷上往往比動態(tài)規(guī)劃要低很多。如何協調好動態(tài)規(guī)劃的高效率與高消費之間的矛盾呢？有一種折中的辦法就是記憶化算法。記憶化算法在求解的時候還是按著自頂向下的順序，每求解一個狀態(tài)，就將它的解保存下來，以后再次遇到這個狀態(tài)的時候，就不必重新求解了。這種方法綜合了搜索和動態(tài)規(guī)劃兩方面的優(yōu)點，因而還是很有使用價值的。舉一個例子：如下圖所示是一個有向無環(huán)圖，求從頂點1到頂點6的最長路徑。（規(guī)定邊的方向從左到右）

我們將從起點（頂點1）開始到某個頂點的最長路徑作為狀態(tài)，用一維數組opt記錄。Opt[j]表示由起點到頂點j時的最長路徑。顯然，opt[1]=0，這是初始狀態(tài)，即動態(tài)規(guī)劃的邊界條件。于是，我們很容易地寫出狀態(tài)轉移方程式：opt[j]=max{opt[k]+a[k][j]}（k到j有一條長度為a[k][j]的邊）。雖然有了完整的狀態(tài)轉移方程式，但是還是不知道動態(tài)規(guī)劃的順序。所以，還需要先進行一下拓撲排序，按照排序的順序推下去，opt[6]就是問題的解?？梢钥闯?，動態(tài)規(guī)劃相比搜索之所以高效，是因為它將所有的狀態(tài)都保存了下來。當遇到重復子問題時，它不像搜索那樣把這個狀態(tài)的最優(yōu)值再計算一遍，只要把那個狀態(tài)的最優(yōu)值調出來就可以了。例如，當計算opt[4]和opt[5]時，都用到了opt[3]的值。因為已經將它保存下來了，所以就沒有必要再去搜索了。但是動態(tài)規(guī)劃仍然是有缺點的。一個很突出的缺點就是要進行拓撲排序。這道題的拓撲關系是很簡單的，但有些題的拓撲關系是很復雜的。對于這些題目，如果也進行拓撲排序，工作量非常大。遇到這種情況，我們可以用記憶化搜索的方法，避免拓撲排序。【例9-26】滑雪【問題描述】

小明喜歡滑雪，因為滑雪的確很刺激，可是為了獲得速度，滑的區(qū)域必須向下傾斜，當小明滑到坡底，不得不再次走上坡或等著直升機來載他，小明想知道在一個區(qū)域中最長的滑坡?；碌拈L度由滑過點的個數來計算，區(qū)域由一個二維數組給出，數組的每個數字代表點的高度。下面是一個例子：

12345 161718196 152425207 142322218 131211109

一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小，在上面的例子中，一條可行的滑坡為25-24-17-16-1（從25開始到1結束），當然25-24……2…1更長，事實上這是最長的一條?！据斎敫袷健?/p>

輸入的第一行為表示區(qū)域的二維數組的行數R和列數C（1≤R、C≤100）下面是R行，每行有C個數代表高度?！据敵龈袷健?/p>

輸出區(qū)域中最長的滑坡長度。[i-1,j]↓[i,j-1]→[i,j]←[i,j+1][i+1,j]↑【輸入樣例】ski.in5512345161718196152425207142322218131211109【輸出樣例】ski.out25【算法分析】

由于一個人可以從某個點滑向上下左右相鄰四個點之一，如上圖所示。當且僅當高度減小，對于任意一個點[i,j]，當它的高度小于與之相鄰的四個點（[i-1,j],[i,j+1],[i+1,j],[i,j-1]）的高度時，這四個點可以滑向[i,j]，用f[i][j]表示到[i,j]為止的最大長度，則f[i][j]=max{f[i+a][j+b]}+1，其中坐標增量{(a,b)=[(1,0),(-1,0),(0,1),(0,-1)],0<i+a<=r，0<j+b<=c，High[i][j]<High[i+a][j+b]}。為了保證滿足條件的f[i+a][j+b]在f[i][j]前算出，需要對高度排一次序，然后從大到小規(guī)劃（高度）。最后再比較一下所有f[i][j]{0<i≤r,0<j≤c}，找出其中最長的一條路線。我們還可以用記憶化搜索的方法，它的優(yōu)點是不需進行排序，按照行的順序，利用遞歸逐點求出區(qū)域中到達此點的最長路徑，每個點的最長路徑只求一次。【參考程序】#include<iostream>#include<cstdio>usingnamespacestd;intdx[5]={0,-1,0,1,0},//x的坐標增量

dy[5]={0,0,1,0,-1};//y的坐標增量longr,c,i,j,p,t,ans;longm[101][101],f[101][101];intsearch(int,int);intmain(){cin>>r>>c;

ans=0;for(i=1;i<=r;i++)for(j=1;j<=c;j++)cin>>m[i][j];//讀入每個點的高度

for(i=1;i<=r;i++)//按照行的順序，利用遞歸逐點求出區(qū)域中到達此點的最長路徑

for(j=1;j<=c;j++){t=search(i,j);f[i][j]=t;if(t>ans)ans=t;//尋找最大長度值

}cout<<ans<<endl;}

intsearch(intx,inty)//函數的作用是求到[x,y]點的最長路徑{inti,t,tmp,nx,ny;

if(f[x][y]>0)//此點長度已經求出，不必進行進一步遞歸，保證每

{//一個點的最大長度只求一次，這是記憶化搜索的特點

return(f[x][y]);}t=1;for(i=1;i<=4;i++)//從四個方向上搜索能達到[x,y]的點

{nx=x+dx[i];//加上橫、縱坐標

ny=y+dy[i];if((nx>=1)&&(nx<=r)&&(ny>=1)&&(ny<=c)&&(m[x][y]<m[nx][ny]))//邊界限制

{//高度比較

tmp=search(nx,ny)+1;//遞歸進行記憶化搜索

if(tmp>t)t=tmp;}}f[x][y]=t;return(t);}【上機練習】1、防衛(wèi)導彈(Catcher.pas)【問題描述】

一種新型的防衛(wèi)導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發(fā)射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈?，F對這種新型防衛(wèi)導彈進行測試，在每一次測試中，發(fā)射一系列的測試導彈（這些導彈發(fā)射的間隔時間固定，飛行速度相同），該防衛(wèi)導彈所能獲得的信息包括各進攻導彈的高度，以及它們發(fā)射次序。現要求編一程序，求在每次測試中，該防衛(wèi)導彈最多能截擊的進攻導彈數量，一個導彈能被截擊應滿足下列兩個條件之一：

1、它是該次測試中第一個被防衛(wèi)導彈截擊的導彈；

2、它是在上一次被截擊導彈的發(fā)射后發(fā)射，且高度不大于上一次被截擊導彈的高度的導彈。【輸入格式】

從當前目錄下的文本文件“CATCHER.IN”讀入數據。該文件的第一行是一個整數N(0<=N<=4000)，表示本次測試中，發(fā)射的進攻導彈數，以下N行每行各有一個整數hi(0<=hi<=32767)，表示第i個進攻導彈的高度。文件中各行的行首、行末無多余空格，輸入文件中給出的導彈是按發(fā)射順序排列的?！据敵龈袷健?/p>

答案輸出到當前目錄下的文本文件“CATCHER.OUT”中，該文件第一行是一個整數max，表示最多能截擊的進攻導彈數，以下的max行每行各有一個整數，表示各個被截擊的進攻導彈的編號（按被截擊的先后順序排列）。輸出的答案可能不唯一，只要輸出其中任一解即可。【輸入輸出樣例】輸入文件：CATCHER.IN

輸出文件：CATCHER.OUT3

225

136

323

2、拔河比賽(tug.pas)【問題描述】

一個學校舉行拔河比賽，所有的人被分成了兩組，每個人必須（且只能夠）在其中的一組，要求兩個組的人數相差不能超過1，且兩個組內的所有人體重加起來盡可能地接近?！据斎敫袷健?/p>

輸入數據的第1行是一個n，表示參加拔河比賽的總人數，n<=100，接下來的n行表示第1到第n個人的體重，每個人的體重都是整數（1<=weight<=450）【輸出格式】

輸出數據應該包含兩個整數：分別是兩個組的所有人的體重和，用一個空格隔開。注意如果這兩個數不相等，則請把小的放在前面輸出?！据斎霕永縯ug.in310090200【輸出樣例】tug.out1902003、求最短距離(distance.pas)【問題描述】小雨家住在小區(qū)里。她今年上小學一年級。每天她都要走路去車站，然后坐車去上學。小區(qū)被道路分成許多正方形的塊，共N*M塊。由于道路太多，她總是迷路。作為程序高手，你幫小雨計算一下從