動(dòng)態(tài)程序設(shè)計(jì)

動(dòng)態(tài)程序設(shè)計(jì)第一頁，共七十一頁，編輯于2023年，星期日基本原理1、多階段最優(yōu)化決策：即由初始狀態(tài)開始，通過對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條最優(yōu)的活動(dòng)路線。第二頁，共七十一頁，編輯于2023年，星期日帶權(quán)有向的多段圖

上一階段的狀態(tài)下一階段的狀態(tài)決策第三頁，共七十一頁，編輯于2023年，星期日概念⑴狀態(tài)（State）：表示事物的性質(zhì)，是描述“動(dòng)態(tài)規(guī)劃”中的“單元”的量。亦是每一階段求解過程的出發(fā)點(diǎn)。⑵階段（Stage）：階段是一些性質(zhì)相近，可以同時(shí)處理的狀態(tài)集合，或者說，階段只是標(biāo)識(shí)那些處理方法相同、處理順序無關(guān)的狀態(tài)。⑶決策（Decision）：每個(gè)階段做出的某種選擇性的行動(dòng)，是程序所需要完成的選擇。⑷狀態(tài)轉(zhuǎn)移方程：是前一個(gè)階段的狀態(tài)轉(zhuǎn)移到后一個(gè)的狀態(tài)的演變規(guī)律，是關(guān)于兩個(gè)相鄰階段狀態(tài)變化的方程，是“動(dòng)態(tài)規(guī)劃”的中心。設(shè)

fk(i)—k階段狀態(tài)i的最優(yōu)權(quán)值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價(jià)

fk+1(i)=min{xk(j)+u(i,j)}

第四頁，共七十一頁，編輯于2023年，星期日基本原理最優(yōu)性原理

作為整個(gè)過程的最優(yōu)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。無后效性原則

給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了。這個(gè)性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個(gè)性質(zhì)稱為無后效性。第五頁，共七十一頁，編輯于2023年，星期日機(jī)器分配

總公司擁有高效生產(chǎn)設(shè)備M臺(tái)，準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備，可以為國家提供一定的盈利。問：如何分配這M臺(tái)設(shè)備才能使國家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原則：每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺(tái)數(shù)不得超過總設(shè)備數(shù)M。數(shù)據(jù)文件格式為：第一行保存兩個(gè)數(shù)，第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M，第二個(gè)數(shù)是分公司數(shù)N。接下來是一個(gè)M*N的矩陣，表明了第I個(gè)公司分配J臺(tái)機(jī)器的盈利。

第六頁，共七十一頁，編輯于2023年，星期日分析用機(jī)器數(shù)來做狀態(tài)，數(shù)組F[I，J]表示前I個(gè)公司分配J臺(tái)機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為:F[I，J]=Max{F[I-1，K]+Value[I，J-K]}(1<=I<=N,1<=J<=M,0<=K<=J)初始值:F(0,0)=0時(shí)間復(fù)雜度O(N*M2)第七頁，共七十一頁，編輯于2023年，星期日最長不下降序列

設(shè)有整數(shù)序列b1,b2,b3,…,bm，若存在下標(biāo)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的序列個(gè)數(shù)。第八頁，共七十一頁，編輯于2023年，星期日分析（1）設(shè)f(i)為前i個(gè)數(shù)中的最大不下降序列長度

,則f(i)=max{f(j)+1}(1<=j<i<=m,bj<bi)邊界為F(1)=1(2)設(shè)t(i)為前i個(gè)數(shù)中最長不下降序列的個(gè)數(shù),則t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)-1)初始為t(i)=1當(dāng)f(i)=n時(shí)，將t(i)累加舉例：

1234658109f:123455677t:111111222答案：f=7時(shí)，邊界為∑t=4第九頁，共七十一頁，編輯于2023年，星期日進(jìn)一步(3)求本質(zhì)不同的最長不下降序列個(gè)數(shù)有多少個(gè)？如：1234658109有，

12346810,12345810,1234689,1234589

都是本質(zhì)不同的。但對(duì)于

1223354f1223354t1112244

答案有8個(gè)，其中4個(gè)1235，4個(gè)1234第十頁，共七十一頁，編輯于2023年，星期日改進(jìn)算法上例顯然對(duì)于相兩個(gè)相同的數(shù)，重復(fù)算了多次因此，我們對(duì)算法進(jìn)行改進(jìn)：對(duì)原序列按b從小到大（當(dāng)bi=bj時(shí)按F從大到?。┡判颍鲈O(shè)Order(i)記錄新序列中的i個(gè)數(shù)在原序列中的位置?？梢?，求t(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)第十一頁，共七十一頁，編輯于2023年，星期日凸多邊形三角劃分

給定一個(gè)具有N（N<50）個(gè)頂點(diǎn)（從1到N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問如何把這個(gè)凸多邊形劃分成N-2個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之和最??？輸入文件：第一行頂點(diǎn)數(shù)N

第二行N個(gè)頂點(diǎn)（從1到N）的權(quán)值輸出格式：最小的和的值各三角形組成的方式輸入示例：5122123245231輸出示例：Theminimumis：12214884Theformationof3triangle:345,153,123第十二頁，共七十一頁，編輯于2023年，星期日分析設(shè)F[I,J]（I<J）表示從頂點(diǎn)I到頂點(diǎn)J的凸多邊形三角剖分后所得到的最大乘積，我們可以得到下面的動(dòng)態(tài)轉(zhuǎn)移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0<I<K<J<=N)初始條件:F[1，2]=0目標(biāo)狀態(tài):F[1,N]但我們可以發(fā)現(xiàn),由于這里為乘積之和，在輸入數(shù)據(jù)較大時(shí)有可能超過長整形范圍，所以還需用高精度計(jì)算

第十三頁，共七十一頁，編輯于2023年，星期日系統(tǒng)可靠性

一個(gè)系統(tǒng)由若干部件串聯(lián)而成，只要有一個(gè)部件故障，系統(tǒng)就不能正常運(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)可能的最高可靠性。

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

…第n行：CnPn(0)Pn(1)…Pn(Xn)（0<=Xn<=[C/Cn]）第十四頁，共七十一頁，編輯于2023年，星期日分析例：輸入：220 30.60.650.70.750.80.850.950.70.750.80.80.90.95輸出：0.6375設(shè)F[I,money]表示將money的資金用到前I項(xiàng)備用件中去的最大可靠性，則有F[I,money]=max{F[I-1,money–k*Cost[I]]}(0<=I<=n,0<=K<=moneydivCost(I))初始：F[0,0]=0目標(biāo)：F[n,C]=0第十五頁，共七十一頁，編輯于2023年，星期日快餐問題

Peter最近在R市開了一家快餐店，為了招攬顧客，該快餐店準(zhǔn)備推出一種套餐，該套餐由A個(gè)漢堡，B個(gè)薯?xiàng)l和C個(gè)飲料組成。價(jià)格便宜。為了提高產(chǎn)量，Peter從著名的麥當(dāng)勞公司引進(jìn)了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡，薯?xiàng)l和飲料，由于每條生產(chǎn)線每天所能提供的生產(chǎn)時(shí)間是有限的、不同的，而漢堡，薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間又不同。這使得Peter很為難，不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請(qǐng)你編一程序，計(jì)算一天中套餐的最大生產(chǎn)量。為簡單起見，假設(shè)漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過100個(gè)。輸入:第一行為三個(gè)不超過100的正整數(shù)A、B、C中間以一個(gè)空格分開。第二行為3個(gè)不超過100的正整數(shù)p1,p2,p3分別為漢堡，薯?xiàng)l和飲料的單位生產(chǎn)耗時(shí)。中間以一個(gè)空格分開。第三行為N(0<=0<=10)，第四行為N個(gè)不超過10000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時(shí)間，中間以一個(gè)空格分開。輸出:每天套餐的最大產(chǎn)量。

第十六頁，共七十一頁，編輯于2023年，星期日分析本題是一個(gè)非常典型的資源分配問題。由于每條生產(chǎn)線的生產(chǎn)是相互獨(dú)立，不互相影響的，所以此題可以以生產(chǎn)線為階段用動(dòng)態(tài)規(guī)劃求解。狀態(tài)表示：用p[i,j,k]表示前i條生產(chǎn)線生產(chǎn)j個(gè)漢堡，k個(gè)薯?xiàng)l的情況下最多可生產(chǎn)飲料的個(gè)數(shù)。用r[i,j,k]表示第i條生產(chǎn)線生產(chǎn)j個(gè)漢堡，k個(gè)薯?xiàng)l的情況下最多可生產(chǎn)飲料的個(gè)數(shù)。態(tài)轉(zhuǎn)移方程

：

p[i,j,k]=Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}(0<=j1<=j<=100,0<=k1<=k<=100,

且(j-j1)*p1+(k-k1)*p2<=T[i]---第i條生產(chǎn)線的生產(chǎn)時(shí)間)r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的時(shí)間復(fù)雜度為O(N*1004),第十七頁，共七十一頁，編輯于2023年，星期日優(yōu)化在本題中，可以在動(dòng)態(tài)規(guī)劃方法中加入了貪心算法思想：即首先計(jì)算出每天生產(chǎn)套數(shù)的上限值（由A,B,C計(jì)算，即min｛100divA，100divB，100divc｝），接著，用貪心法計(jì)算出這N條流水線可以生產(chǎn)的套數(shù)，并與上限比較，大于則輸出上限值并退出，否則再調(diào)用動(dòng)態(tài)規(guī)劃；同時(shí)，在運(yùn)行動(dòng)態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進(jìn)行比較，這樣以來，便可望在動(dòng)態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計(jì)為：S1：讀入數(shù)據(jù)。S2：貪心求上限并計(jì)算出一可行解，判斷是否需進(jìn)行下一步。S3：動(dòng)態(tài)規(guī)劃求解。S4：輸出。第十八頁，共七十一頁，編輯于2023年，星期日其他優(yōu)化方法1.存儲(chǔ)結(jié)構(gòu)：由于每一階段狀態(tài)只與上一階段狀態(tài)有關(guān)，所以我們可以只用兩個(gè)100*100的數(shù)組滾動(dòng)實(shí)現(xiàn)。但考慮到滾動(dòng)是有大量的賦值，可以改進(jìn)為動(dòng)態(tài)數(shù)組，每次交換時(shí)只需交換指針即可，這樣比原來數(shù)組間賦值要快。2.減少循環(huán)次數(shù)：在計(jì)算每一階段狀態(tài)過程中無疑要用到4重循環(huán)，我們可以這樣修改每一重循環(huán)的起始值和終數(shù)，其中q1,q2為A，B上限值。原起始值

改進(jìn)后的起始值fori:=1tondofori:=1tondoforj:=0totot[i]divp1doforj:=0tomin(q1,tot[i]divp1)dofork:=0to(tot[i]-p1*j)divp2dofork:=0tomin(q2,(tot[i]-p1*j)divp2)doforj1:=0tojdoforj1:=max(0,j-t[i]divp1)tomin(j,tot[i-1]divp1)dofork1:=0tokdofork1:=max(0,k-(t[i]-(j-j1)*p1)divp2)tomin(k,(tot[i-1]-p1*j1)divp2)do第十九頁，共七十一頁，編輯于2023年，星期日石子合并在一園形操場四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(≤20), (1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少(2)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大輸入數(shù)據(jù):

第一行為石子堆數(shù)N;

第二行為每堆石子數(shù),每兩個(gè)數(shù)之間用一空格分隔.輸出數(shù)據(jù):

從第1至第N行為得分最小的合并方案.第N+1行為空行.從N+2到2N+1行是得分最大的合并方案.第二十頁，共七十一頁，編輯于2023年，星期日示例第二十一頁，共七十一頁，編輯于2023年，星期日貪心法N=5石子數(shù)分別為346542。用貪心法的合并過程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24總分：62然而仔細(xì)琢磨后，發(fā)現(xiàn)更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24總分：61顯然，貪心法是錯(cuò)誤的。第二十二頁，共七十一頁，編輯于2023年，星期日動(dòng)態(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這樣，我們完美地解決了這道題。時(shí)間復(fù)雜度也是O(n2)。第二十三頁，共七十一頁，編輯于2023年，星期日積木游戲一種積木游戲，游戲者有N塊編號(hào)依次為1，2，…，N的長方體積木。第I塊積木通過同一頂點(diǎn)三條邊的長度分別為ai,bi,ci（i=1,2,…,N），1從N塊積木中選出若干塊，并將他們摞成M（1<=M<=N）根柱子，編號(hào)依次為1,2,…,M，要求第k根柱子的任意一塊積木的編號(hào)都必須大于第K-1根柱子任意一塊積木的編號(hào)（2<=K<=M）。2對(duì)于每一根柱子，一定要滿足下面三個(gè)條件：除最頂上的一塊積木外，任意一塊積木的上表面同且僅同另一塊積木的下表面接觸；對(duì)于任意兩塊上下表面相接觸的積木，若m,n是下面一塊積木接觸面的兩條邊（m>=n），x,y是上面一塊積木接觸面的兩條邊（x>=y），則一定滿足m.>=x和n>=y；下面的積木的編號(hào)要小于上面的積木的編號(hào)。請(qǐng)你編一程序，尋找一種游戲方案，使得所有能摞成的M根柱子的高度之和最大。第二十四頁，共七十一頁，編輯于2023年，星期日積木游戲輸入數(shù)據(jù)：文件的第一行是兩個(gè)正整數(shù)N和M（1<=M<=N<=100）,分別表示積木總數(shù)和要求摞成的柱子數(shù)。這兩個(gè)數(shù)之間用一個(gè)空格符隔開。接下來的N行是編號(hào)從1到N個(gè)積木的尺寸，每行有三個(gè)1至500之間的整數(shù)，分別表示該積木三條邊的長度。同一行相鄰兩個(gè)數(shù)之間用一個(gè)空格符隔開。輸出數(shù)據(jù)：文件只有一行，是一個(gè)整數(shù)，表示所求得的游戲方案中M根柱子的高度之和第二十五頁，共七十一頁，編輯于2023年，星期日分析設(shè)（1）f[i,j,k]表示以第i塊積木的第k面為第j根柱子的頂面的最優(yōu)方案的高度總和；（2）block[i,k]記錄每個(gè)積木的三條邊信息（block[i,4]:=block[i,1];block[i,5]:=block[i,2]）。其中block[i,j+2]表示當(dāng)把第i塊積木的第j面朝上時(shí)所對(duì)應(yīng)的高，即所增加的高度；（3）can[i,k,p,kc]表示第I塊積木以其第k面朝上，第p塊積木以第kc面朝上時(shí)，能否將積木I放在積木p的上面。1表示能，0表示不能。對(duì)于f[i,j,k],有兩種可能：

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

2.第i塊積木是第j根柱子的第一塊積木，第j-1根柱子的最上面為第p塊積木，則此時(shí)第p塊積木可以以任意一面朝上。則有：第二十六頁，共七十一頁，編輯于2023年，星期日動(dòng)態(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);時(shí)間復(fù)雜度為O(n^2*m)第二十七頁，共七十一頁，編輯于2023年，星期日免費(fèi)餡餅SERKOI最新推出了一種叫做“免費(fèi)餡餅”的游戲。游戲在一個(gè)舞臺(tái)上進(jìn)行。舞臺(tái)的寬度為W格，天幕的高度為H格，游戲者占一格。開始時(shí)，游戲者站在舞臺(tái)的正中央，手里拿著一個(gè)托盤。游戲開始后，從舞臺(tái)天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動(dòng)去接餡餅。游戲者每秒可以向左或右移動(dòng)一格或兩格，也可以站在愿地不動(dòng)。餡餅有很多種，游戲者事先根據(jù)自己的口味，對(duì)各種餡餅依次打了分。同時(shí)在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就收集到了這塊餡餅。寫一個(gè)程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分?jǐn)?shù)之和最大。第二十八頁，共七十一頁，編輯于2023年，星期日免費(fèi)餡餅輸入數(shù)據(jù)：輸入文件的第一行是用空格分開的兩個(gè)正整數(shù)，分別給出了舞臺(tái)的寬度W（1~99之間的奇數(shù)）和高度H（1~100之間的整數(shù)）。接下來依餡餅的初始下落時(shí)間順序給出了一塊餡餅信息。由四個(gè)正整數(shù)組成，分別表示了餡餅的初始下落時(shí)刻（0~1000秒），水平位置、下落速度（1~100）以及分值。游戲開始時(shí)刻為0。從1開始自左向右依次對(duì)水平方向的每格編號(hào)。輸出數(shù)據(jù)：輸出文件的第一行給出了一個(gè)正整數(shù)，表示你的程序所收集到的最大分?jǐn)?shù)之和。第二十九頁，共七十一頁，編輯于2023年，星期日分析我們將問題中的餡餅信息用一個(gè)表格存儲(chǔ)。表格的第I行第J列表示的是游戲者在第I秒到達(dá)第J列所能取得的分值。那么問題便變成了一個(gè)類似數(shù)字三角形的問題：從表格的第一行開始往下走，每次只能向左或右移動(dòng)一格或兩格，或不移動(dòng)走到下一行。怎樣走才能得到最大的分值。因此，我們很容易想到用動(dòng)態(tài)規(guī)劃求解。F[I,J]表示游戲進(jìn)行到第I秒，這時(shí)游戲者站在第J列時(shí)所能得到的最大分值。那么動(dòng)態(tài)轉(zhuǎn)移方程為：

F[I,J]=Max{F[I-1,K]}+餡餅的分值

(J-2<=K<=J+2)第三十頁，共七十一頁，編輯于2023年，星期日有一個(gè)三角形木板,豎直立放，上面釘著n(n+1)/2顆釘子，還有(n+1)個(gè)格子（當(dāng)n=5時(shí)如圖1）。每顆釘子和周圍的釘子的距離都等于d，每個(gè)格子的寬度也都等于d，且除了最左端和最右端的格子外每個(gè)格子都正對(duì)著最下面一排釘子的間隙。讓一個(gè)直徑略小于d的小球中心正對(duì)著最上面的釘子在板上自由滾落，小球每碰到一個(gè)釘子都可能落向左邊或右邊（概率各1/2），且球的中心還會(huì)正對(duì)著下一顆將要碰上的釘子。例如圖2就是小球一條可能的路徑。我們知道小球落在第i個(gè)格子中的概率pi=，其中i為格子的編號(hào)，從左至右依次為0,1,...,n。現(xiàn)在的問題是計(jì)算拔掉某些釘子后，小球落在編號(hào)為m的格子中的概率pm。假定最下面一排釘子不會(huì)被拔掉。例如圖3是某些釘子被拔掉后小球一條可能的路徑。釘子和小球第三十一頁，共七十一頁，編輯于2023年，星期日釘子和小球輸入：第1行為整數(shù)n（2<=n<=50）和m（0<=m<=n）。以下n行依次為木板上從上至下n行釘子的信息，每行中‘*’表示釘子還在，‘.’表示釘子被拔去，注意在這n行中空格符可能出現(xiàn)在任何位置。輸出：僅一行，是一個(gè)既約分?jǐn)?shù)(0寫成0/1)，為小球落在編號(hào)為m的格子中的概率pm第三十二頁，共七十一頁，編輯于2023年，星期日分析設(shè)三角形有n行，第i行（1<=i<=n）有i個(gè)鐵釘位置，其編號(hào)為0..i-1；第n+1行有n+1個(gè)鐵釘位置，排成n+1個(gè)格子，編號(hào)為0..n。設(shè)經(jīng)過位置（i,j）的小球個(gè)數(shù)為Pi,j，則落入格子m的小球個(gè)數(shù)為Pn+1,m，問題要求的是Pn+1,m/2n。假設(shè)位置(i,j)有鐵釘，則各有Pi,j/2個(gè)小球落入位置（i+1,j）和位置(i+1,j+1)；否則Pi,j

個(gè)小球?qū)⑷柯淙胛恢?i+2,j+1)。可得如下算法：

P1,0←2n; fori←1tondo forj←1tondoif位置(i,j)有釘子then {Pi+1,j←Pi+1,j+Pi,j/2; Pi+1,j+1←Pi+1,j+1+Pi,j/2; }elsePi+2,j+1←Pi+2,j+1+Pi,j;問題求的是既約分?jǐn)?shù)，因?yàn)榉帜笧?的次冪，因此可把分子、分母同時(shí)約去2的因子，直至分子不能整除2。第三十三頁，共七十一頁，編輯于2023年，星期日商店購物 某商店中每種商品都有一個(gè)價(jià)格。例如，一朵花的價(jià)格是2ICU(ICU是信息學(xué)競賽的貨幣的單位）;一個(gè)花瓶的價(jià)格是5ICU。為了吸引更多的顧客，商店提供了特殊優(yōu)惠價(jià)。特殊優(yōu)惠商品是把一種或幾種商品分成一組。并降價(jià)銷售。例如:3朵花的價(jià)格不是6而是5ICU;2個(gè)花瓶加1朵花是10ICU不是12ICU。編一個(gè)程序，計(jì)算某個(gè)顧客所購商品應(yīng)付的費(fèi)用。要充分利用優(yōu)惠價(jià)以使顧客付款最小。請(qǐng)注意，你不能變更顧客所購商品的種類及數(shù)量，即使增加某些商品會(huì)使付款總數(shù)減小也不允許你作出任何變更。假定各種商品價(jià)格用優(yōu)惠價(jià)如上所述，并且某顧客購買物品為:3朵花和2個(gè)花瓶。那么顧客應(yīng)付款為14ICU因?yàn)?1朵花加2個(gè)花瓶:優(yōu)惠價(jià):10ICU2朵花正常價(jià):4ICU第三十四頁，共七十一頁，編輯于2023年，星期日商店購物輸入數(shù)據(jù)第一個(gè)文件INPUT．TXT的格式為:第一行是一個(gè)數(shù)字B（0≤B≤5），表示所購商品種類數(shù)。下面共B行，每行中含3個(gè)數(shù)C，K，P。C代表商品的編碼（每種商品有一個(gè)唯一的編碼），1≤C≤999。K代表該種商品購買總數(shù)，1≤K≤5。P是該種商品的正常單價(jià)（每件商品的價(jià)格），1≤P≤999。請(qǐng)注意，購物筐中最多可放5*5＝25件商品。第二個(gè)文件OFFER．TXT的格式為:第一行是一個(gè)數(shù)字S（0≤S≤99），表示共有S種優(yōu)惠。下面共S行，每一行描述一種優(yōu)惠商品的組合中商品的種類。下面接著是幾個(gè)數(shù)字對(duì)（C，K），其中C代表商品編碼，1≤C≤999。K代表該種商品在此組合中的數(shù)量，1≤K≤5。本行最后一個(gè)數(shù)字P（1≤P≤9999）代表此商品組合的優(yōu)惠價(jià)。當(dāng)然，優(yōu)惠價(jià)要低于該組合中商品正常價(jià)之總和。輸出數(shù)據(jù)在輸出文件OUTPUT．TXT中寫一個(gè)數(shù)字（占一行），該數(shù)字表示顧客所購商品（輸入文件指明所購商品）應(yīng)付的最低貨款。

第三十五頁，共七十一頁，編輯于2023年，星期日分析由于動(dòng)態(tài)規(guī)劃要滿足無后效性和最優(yōu)化原理，所以我們來分析此題是否滿足以上兩點(diǎn)。首先確定狀態(tài)，商品不超過5種，而每種采購的數(shù)量又不超過5，那么用一個(gè)五元組來表示第i種商品買Ai的最小費(fèi)用。F（A1，A2，A3，A4，A5）

（1）考慮這個(gè)狀態(tài)的由來，當(dāng)然，我們不用優(yōu)惠商品也可以買，顯然這樣不是最優(yōu)。于是如果我們能夠使用第i條商品組合的話，狀態(tài)就b變?yōu)榱耍篎（A1-SI1，A2-SI2，A3-SI3，A4-SI4，A5-SI5）

（2）這樣的話，狀態(tài)1的費(fèi)用為狀態(tài)2的費(fèi)用加上Si的費(fèi)用，而狀態(tài)2的費(fèi)用必須最低（很顯然，用反證法即可），同時(shí)，我們也不管狀態(tài)2是如何來的（因?yàn)槊恳粋€(gè)優(yōu)惠商品組合的使用是沒有限制的），所以本題既滿足無后效性，又符合最優(yōu)化原理，同時(shí)還有大量重疊子問題產(chǎn)生，動(dòng)態(tài)規(guī)劃解決此題是最好不過了。第三十六頁，共七十一頁，編輯于2023年，星期日狀態(tài)轉(zhuǎn)移方程F[a,b,c,d,e]=Min{F[a-Si1,b-Si2,c-Si3,d-Si4,e-Si5]+SaleCost[Si]}(0<=i<=S,0<=a,b,c,d,e<=5)初始條件為：

F[a,b,c,d,e]=Cost[1]*a+Cost[2]*b+Cost[3]*c+Cost[4]*d+Cost[5]*e第三十七頁，共七十一頁，編輯于2023年，星期日添括號(hào)問題

有一個(gè)由數(shù)字1，2，...，9組成的數(shù)字串（長度不超過200），問如何將M(M<=20)個(gè)加號(hào)("+")插入到這個(gè)數(shù)字串中，使所形成的算術(shù)表達(dá)式的值最小。請(qǐng)編一個(gè)程序解決這個(gè)問題。注意：加號(hào)不能加在數(shù)字串的最前面或最末尾，也不應(yīng)有兩個(gè)或兩個(gè)以上的加號(hào)相鄰。M保證小于數(shù)字串的長度。例如：數(shù)字串79846，若需要加入兩個(gè)加號(hào)，則最佳方案為79+8+46，算術(shù)表達(dá)式的值133。[輸入格式］從鍵盤讀入輸入文件名。數(shù)字串在輸入文件的第一行行首（數(shù)字串中間無空格且不折行），Ｍ的值在輸入文件的第二行行首。[輸出格式］在屏幕上輸出所求得的最小和的精確值。第三十八頁，共七十一頁，編輯于2023年，星期日分析考慮到數(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個(gè)數(shù)字中添上I個(gè)加號(hào)后得到的最小值。NUM[I，J]表示數(shù)字串第I位到第J位的數(shù)上述問題的每一步，都只與上一步有關(guān)。因此可以采用滾動(dòng)數(shù)組程序的時(shí)間效率約為20*200*200第三十九頁，共七十一頁，編輯于2023年，星期日最長前綴

一些生物體的復(fù)雜結(jié)構(gòu)可以用其基元的序列表示，而一個(gè)基元用一個(gè)大寫英文字符串表示。生物學(xué)家的一個(gè)問題就是一個(gè)這樣的長序列分解為基元（字符串）的序列。對(duì)于給定的基元集合P，如果可以從中選出N個(gè)基元P1，P2，P3，...,Pn，將它們各自對(duì)應(yīng)的字符串依次連接后得到一個(gè)字符串S，稱S可以由基元集合P構(gòu)成。在從P中挑選基元時(shí)，一個(gè)基元可以使用多次，也可不用。例如，序列ABABACABAAB可以由基元集合{A，AB，BA，CA，BBC}構(gòu)成。字符串的前K個(gè)字符為該字符串的前綴，其長度為K。請(qǐng)寫一個(gè)程序，對(duì)于輸入的基元集合P和字符串T，求出一個(gè)可以由基元集合P構(gòu)成的字符串T的前綴，要求該前綴的長度盡可能長，輸出其長度。第四十頁，共七十一頁，編輯于2023年，星期日最長前綴輸入數(shù)據(jù)：有兩個(gè)輸入文件INPUT.TXT，DATA.TXT INPUT.TXT的第一行是基元集合P中的基元數(shù)目N（1<=N<=100）,隨后有2N行，每兩行描述一個(gè)基元，第一行為該基元的長度L（1<=L<=20）。隨后一行是一個(gè)長度為L的大寫英文字符串，表示該基元。每個(gè)基元互不相同。

DATA.TXT描述要處理的字符串T，每一行行首有一個(gè)大寫字母，最后一行是一個(gè)字符‘.’,表示字符串結(jié)束。T的長度最小為1，最大不超過500000。輸出數(shù)據(jù)：OUTPUT.TXT。只有一行，一個(gè)數(shù)字，表示可以由P構(gòu)成的T的最長前綴的長度。第四十一頁，共七十一頁，編輯于2023年，星期日分析本題可以簡述為:從一個(gè)集合里選出若干個(gè)基元,使其組成字符串T的前綴,求最長前綴的長度.對(duì)于T的每個(gè)字符，其狀態(tài)可分為兩種：在此之前的所有字符（包括本身）可匹配(true)、不可匹配(false)。(可匹配是指可以由集合里的基元組成)用Fi表示第i個(gè)字符的狀態(tài)，finda,b表示由第a至b位的字符組成的子串是否存在于集合中，則， Fi=Fior(Fkandfindk+1,j)(0<=k<=i-1)初始條件: ifi=0thenFi:=trueelseFi:=false第四十二頁，共七十一頁，編輯于2023年，星期日分析由于T的長度最大達(dá)500000，無法存放所有狀態(tài)，但集合里基元長度不超過20，因此可只保留當(dāng)前20位字符與狀態(tài)。當(dāng)20位字符都不可以匹配時(shí)，停止運(yùn)算，最后一個(gè)狀態(tài)為true的字符的位置，即為所求。為了便于操作，可用字符串表示狀態(tài)，‘0’表false、‘1’表true.為了便于查找，可將基元按長度存儲(chǔ)。形如：s[i,j]，表示長度為i的第j個(gè)基元。亦可采用樹的結(jié)構(gòu)存儲(chǔ)基元，構(gòu)造一種多叉樹（最多26叉），查找時(shí)順著相應(yīng)字母，定位到相應(yīng)分支。這樣速度要快些，但程序更復(fù)雜。大家可以比較一下。按樹結(jié)構(gòu)算，時(shí)間復(fù)雜度為O(500000*L*L),勉強(qiáng)可以承受。第四十三頁，共七十一頁，編輯于2023年，星期日多邊形

多角形是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)N個(gè)頂點(diǎn)的多邊形。如圖，這里N=4。每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記，每條邊上有一個(gè)“+”號(hào)或“*”號(hào)。邊從1編號(hào)到N。第一步，一條邊被拿走；隨后各步包括如下：

選擇一條邊E和連接著E的兩個(gè)頂點(diǎn)V1和V2；得到一個(gè)新的頂點(diǎn)，標(biāo)記為V1與V2通過邊E上的運(yùn)算符運(yùn)算的結(jié)果。最后，游戲中沒有邊，游戲的得分為僅剩余的一個(gè)頂點(diǎn)的值。

第四十四頁，共七十一頁，編輯于2023年，星期日樣例寫一個(gè)程序，對(duì)于給定一個(gè)多邊形，計(jì)算出可能的最高得分，并且列出得到這個(gè)分?jǐn)?shù)的過程。第四十五頁，共七十一頁，編輯于2023年，星期日分析

第四十六頁，共七十一頁，編輯于2023年，星期日分析我們?cè)谶@條“線”當(dāng)中繼續(xù)刪邊，并且每次刪邊都使被刪邊兩旁的點(diǎn)按邊上的操作符合并，圖五。這樣進(jìn)行了n-1次刪邊操作后，“線” 變成了一個(gè)點(diǎn)。我們的目的，就是安排刪邊的順序，使最后的點(diǎn)上的數(shù)盡可能的大。拿到題目之后，我們馬上可以想到用枚舉法——枚舉刪邊的先后順序。但邊數(shù)最大可以達(dá)到50，枚舉的復(fù)雜將會(huì)有50！。因此枚舉算法馬上被排除了。

對(duì)最優(yōu)化問題的求解，我們往往可以使用動(dòng)態(tài)規(guī)劃來解決。這道題是不是可以使用動(dòng)態(tài)規(guī)劃呢？我們先對(duì)題目進(jìn)行一些變化——原題中頂點(diǎn)上的數(shù)可以為負(fù)數(shù)，現(xiàn)在我們規(guī)定這個(gè)數(shù)一定大于等于0；原題中邊可以為乘號(hào)，現(xiàn)在我們規(guī)定只能為加號(hào)。題意改變后，我們想到了什么？對(duì)！“石子合并”。第四十七頁，共七十一頁，編輯于2023年，星期日動(dòng)態(tài)規(guī)劃我們先枚舉第一次刪掉的邊，然后再對(duì)每種狀態(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求最大值

用f(I,j)表示從j開始，進(jìn)行i次刪邊操作所能得到的最大值，num(i)表示第i個(gè)頂點(diǎn)上的數(shù)，那么：第四十八頁，共七十一頁，編輯于2023年，星期日進(jìn)一步分析現(xiàn)在我們來考慮加入乘號(hào)后的情況。由于所有的頂點(diǎn)上的數(shù)都為非負(fù)數(shù)，因此即使有了乘法，函數(shù)f的無后效性并不被破壞。我們可以在前一方程的基礎(chǔ)上進(jìn)行改進(jìn)：（opr(i)表示第i條邊上的操作符）

第四十九頁，共七十一頁，編輯于2023年，星期日進(jìn)一步分析最后，我們?cè)试S頂點(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**圖六+第五十頁，共七十一頁，編輯于2023年，星期日最終？我們引入函數(shù)fmin和fmax來解決這個(gè)問題。fmax(I,j)表示從j開始，進(jìn)行i次刪邊操作所能得到的最大值，fmin(I,j)表示從j開始，進(jìn)行i次刪邊操作所能得到的最小值。函數(shù)actmax與actmin的構(gòu)造是十分關(guān)鍵的。首先討論actmax(x1,y1,x2,y2)的構(gòu)造：當(dāng)opr(x2-1)=+時(shí)，actmax=fmax(x1,y1)+fmax(x2,y2)當(dāng)opr(x2-1)=*時(shí)，

actmax=max(fmax(x1,y1)*fmax(x2,y2),fmin(x1,y1)*fmin(x2,y2))

第五十一頁，共七十一頁，編輯于2023年，星期日完美解決接下來討論actmin(x1,y1,x2,y2)的構(gòu)造：當(dāng)opr(x2-1)=+時(shí)，actmin=fmin(x1,y1)+fmin(x2,y2)opr(x2-1)=*時(shí)，

actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2))到此為止，整個(gè)問題圓滿解決了。算法的空間復(fù)雜度為n2，算法時(shí)間復(fù)雜度為n4（先要枚舉每一條邊，然后再用復(fù)雜度為n3的動(dòng)態(tài)規(guī)劃解決）。第五十二頁，共七十一頁，編輯于2023年，星期日選課

大學(xué)里實(shí)行學(xué)分。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并考核通過就能獲得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門課的學(xué)分的總和。每個(gè)學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識(shí)，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如，《數(shù)據(jù)結(jié)構(gòu)》必須在選修了《高級(jí)語言程序設(shè)計(jì)》之后才能選修。我們稱《高級(jí)語言程序設(shè)計(jì)》是《數(shù)據(jù)結(jié)構(gòu)》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每門課都有一個(gè)課號(hào)，課號(hào)依次為1，2，3，……。

第五十三頁，共七十一頁，編輯于2023年，星期日選課下面舉例說明上例中1是2的先修課，即如果要選修2，則1必定已被選過。同樣，如果要選修3，那么1和2都一定已被選修過。學(xué)生不可能學(xué)完大學(xué)所開設(shè)的所有課程，因此必須在入學(xué)時(shí)選定自己要學(xué)的課程。每個(gè)學(xué)生可選課程的總數(shù)是給定的。現(xiàn)在請(qǐng)你找出一種選課方案，使得你能得到學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時(shí)間上的沖突。第五十四頁，共七十一頁，編輯于2023年，星期日選課

輸入

輸入文件的第一行包括兩個(gè)正整數(shù)M、N（中間用一個(gè)空格隔開）其中M表示待選課程總數(shù)（1≤M≤1000)，N表示學(xué)生可以選的課程總數(shù)（1≤N≤M)。

以下M行每行代表一門課，課號(hào)依次為1，2……M。每行有兩個(gè)數(shù)（用一個(gè)空格隔開），第一個(gè)數(shù)為這門課的先修課的課號(hào)（若不存在先修課則該項(xiàng)為0），第二個(gè)數(shù)為這門課的學(xué)分。學(xué)分是不超過10的正整數(shù)。輸出

輸出文件第一行只有一個(gè)數(shù)，即實(shí)際所選課程的學(xué)分總數(shù)。以下N行每行有一個(gè)數(shù)，表示學(xué)生所選課程的課號(hào)。第五十五頁，共七十一頁，編輯于2023年，星期日樣例分析7422010421717622表12157346圖202157346圖1第五十六頁，共七十一頁，編輯于2023年，星期日分析們可以選取某一個(gè)點(diǎn)k的條件只是它的父節(jié)點(diǎn)已經(jīng)被選取或者它自己為根節(jié)點(diǎn)；而且我們不論如何取k的子孫節(jié)點(diǎn)，都不會(huì)影響到它父節(jié)點(diǎn)的選取情況，這滿足無后效性原則。于是我們猜測，是不是可以以節(jié)點(diǎn)為階段，進(jìn)行動(dòng)態(tài)規(guī)劃呢？我們用函數(shù)f(I,j)表示以第i個(gè)節(jié)點(diǎn)為父節(jié)點(diǎn)，取j個(gè)子節(jié)點(diǎn)的最佳代價(jià)，則：可是如此規(guī)劃，其效率與搜索毫無差別，雖然我們可以再次用動(dòng)態(tài)規(guī)劃來使它的復(fù)雜度變?yōu)槠椒郊?jí)，但顯得過于麻煩。第五十七頁，共七十一頁，編輯于2023年，星期日改造樹轉(zhuǎn)變?yōu)槎鏄?。如果兩?jié)點(diǎn)a,b同為兄弟，則將b設(shè)為a的右節(jié)點(diǎn)；如果節(jié)點(diǎn)b是節(jié)點(diǎn)a的兒子，則將節(jié)點(diǎn)b設(shè)為節(jié)點(diǎn)a的左節(jié)點(diǎn)。樹改造完成后如圖3。我們用函數(shù)f(I,j)表示以第i個(gè)節(jié)點(diǎn)為父節(jié)點(diǎn)，取j個(gè)子節(jié)點(diǎn)的最佳代價(jià)，這和前一個(gè)函數(shù)表示的意義是一致的，但方程有了很大的改變：023014765圖3第五十八頁，共七十一頁，編輯于2023年，星期日動(dòng)態(tài)規(guī)劃這個(gè)方程的時(shí)間復(fù)雜度最大為n3，十分優(yōu)秀了。在具體實(shí)現(xiàn)這道題時(shí)，我們可以自頂而下，用遞歸進(jìn)行樹的遍歷求解

第五十九頁，共七十一頁，編輯于2023年，星期日隕石的秘密

公元11380年，一顆巨大的隕石墜落在南極。于是，災(zāi)難降臨了，地球上出現(xiàn)了一系列反常的現(xiàn)象。當(dāng)人們焦急萬分的時(shí)候，一支中國科學(xué)家組成的南極考察隊(duì)趕到了出事地點(diǎn)。經(jīng)過一番偵察，科學(xué)家們發(fā)現(xiàn)隕石上刻有若干行密文，每一行都包含5個(gè)整數(shù)：11116006357801132845著名的科學(xué)家SS發(fā)現(xiàn)，這些密文實(shí)際上是一種復(fù)雜運(yùn)算的結(jié)果。為了便于大家理解這種運(yùn)算，他定義了一種SS表達(dá)式：

第六十頁，共七十一頁，編輯于2023年，星期日隕石的秘密1．

SS表達(dá)式是僅由‘{’，‘}’，‘[’，‘]’，‘（’，‘）’組成的字符串。2．

一個(gè)空串是SS表達(dá)式。3．

如果A是SS表達(dá)式，且A中不含字符‘{’，‘}’，‘[’，‘]’，則(A)是SS表達(dá)式。4．

如果A是SS表達(dá)式，且A中不含字符‘{’，‘}’，則[A]是SS表達(dá)式。5．

如果A是SS表達(dá)式，則{A}是SS表達(dá)式。6．如果A和B都是SS表達(dá)式