動態(tài)規(guī)劃幻燈片-king

動態(tài)規(guī)劃（DP）在分治算法中，為了解決一個大問題，我們總是將它分解成兩個或更多的小問題，然后分別解決每個小問題，再把各小問題的解答組合起來就得到原來問題的借。小問題通常和原問題本質(zhì)相似，只是規(guī)模小些，一般都可以用遞歸的方法來解決，如漢諾塔問題和快速排序都是例子。有些問題當(dāng)把問題分解成子問題，使之能夠從這些子問題的借得到原問題的解時，子問題的數(shù)目太多，如果把每個子問題再分解，必將得到更多的子問題，以至于最后解決問題需要耗費指數(shù)級的時間。其實，在這類問題中，子問動態(tài)規(guī)劃-king的數(shù)目只是多項式個，于是在上述算法中，一定有些子問題被重復(fù)計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時簡單查一下，這樣我們可以避免大量的重復(fù)計算為了實現(xiàn)上述方法，我們用一個數(shù)組記錄所有已解決的子問題的答案，無論子問題以后是否被用到，只要它被計算過，就將其結(jié)果存入數(shù)組中，這種方法在程序設(shè)計中被稱為動態(tài)規(guī)劃（DP）動態(tài)規(guī)劃-king動態(tài)規(guī)劃簡介

動態(tài)規(guī)劃是運籌學(xué)的一個分支。它是解決多階段決策過程最優(yōu)化問題的一種方法。1951年，美國數(shù)學(xué)家貝爾曼（R.Bellman）提出了解決這類問題的“最優(yōu)化原則”，1957年發(fā)表了他的名著《動態(tài)規(guī)劃》，該書是動態(tài)規(guī)劃方面的第一本著作。動態(tài)規(guī)劃問世以來，在工農(nóng)業(yè)生產(chǎn)、經(jīng)濟、軍事、工程技術(shù)等許多方面都得到了廣泛的應(yīng)用，取得了顯著的效果。

動態(tài)規(guī)劃-king動態(tài)規(guī)劃簡介動態(tài)規(guī)劃運用于信息學(xué)競賽是在90年代初期，它以獨特的優(yōu)點獲得了出題者的青睞。此后，它就成為了信息學(xué)競賽中必不可少的一個重要方法，幾乎在所有的國內(nèi)和國際信息學(xué)競賽中，都至少有一道動態(tài)規(guī)劃的題目。所以，掌握好動態(tài)規(guī)劃，是非常重要的。

動態(tài)規(guī)劃-king動態(tài)規(guī)劃簡介動態(tài)規(guī)劃是一種方法，是考慮問題的一種途徑，而不是一種算法。因此，它不像深度優(yōu)先和廣度優(yōu)先那樣可以提供一套模式。它必須對具體問題進行具體分析。需要豐富的想象力和創(chuàng)造力去建立模型求解。

動態(tài)規(guī)劃-king動態(tài)規(guī)劃思路：用一個數(shù)組來記錄所有已解決的子問題的答案。無論子問題以后是否被用到，只要它被計算過，就將其結(jié)果存入數(shù)組中，這種方法在程序設(shè)計中被稱為動態(tài)規(guī)劃。相比較分治算法，提高了程序效率。動態(tài)規(guī)劃-king最短路徑問題如圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。

動態(tài)規(guī)劃-king以上求從A到E的最短路徑問題，可以轉(zhuǎn)化為三個性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從B1、B2、B3到E的最短路徑問題。記從Bi(i=1,2,3)到E的最短路徑為S(Bi)，則從A到E的最短距離S(A)可以表示為：

動態(tài)規(guī)劃-king同樣，計算S(B1)又可以歸結(jié)為性質(zhì)完全相同，但規(guī)模更小的問題，即分別求C1，C2，C3到E的最短路徑問題S(Ci)(i=1,2,3)，而求S(Ci)又可以歸結(jié)為求S(D1)和S(D2)這兩個子問題。從圖1.1.1可以看出，在這個問題中，S(D1)和S(D2)是已知的，它們分別是： S(D1)=5，S(D2)=2動態(tài)規(guī)劃-king因而，可以從這兩個值開始，逆向遞歸計算S(A)的值。計算過程如下：

動態(tài)規(guī)劃-king即

S(C1)=8 且如果到達(dá)C1，則下一站應(yīng)到達(dá)D1； S(C2)=7 且如果到達(dá)C2，則下一站應(yīng)到達(dá)D2； S(C3)=12 且如果到達(dá)C3，則下一站應(yīng)到達(dá)D2；動態(tài)規(guī)劃-king即

S(B1)=20 且如果到達(dá)B1，則下一站應(yīng)到達(dá)C1； S(B2)=14 且如果到達(dá)B2，則下一站應(yīng)到達(dá)C1； S(B3)=19 且如果到達(dá)B3，則下一站應(yīng)到達(dá)C2；

動態(tài)規(guī)劃-king動態(tài)規(guī)劃-king圖的鄰接矩陣如下：0251-1-1-1-1-1-1

-10-1-11214-1-1-1-1

-1-10-16104-1-1-1

-1-1-10131211-1-1-1

-1-1-1-10-1-139-1

-1-1-1-1-10-165-1

-1-1-1-1-1-10-110-1

-1-1-1-1-1-1-10-15

-1-1-1-1-1-1-1-102

-1-1-1-1-1-1-1-1-10采用逆推法設(shè)f（x）表示點x到v10的最短路徑長度則f(10)=0

f(x)=min{f(i)+a[x，i]當(dāng)a[x，i]>0,x<i<=n}動態(tài)規(guī)劃-king如何記錄路徑：１記錄數(shù)字標(biāo)志；２順序或遞歸實現(xiàn)vari,j,k,m,n:longint;weight,cost:array[1..1000]oflongint;f,ff:array[0..1000,0..1000]oflongint;procedureos(i,j:longint);beginif(i=0)or(j=0)thenexit;caseff[i,j]of1:os(i-1,j);2:beginos(i-1,j-weight[i]);write(i,'');end;end;end;beginassign(input,'bag01.in');reset(input);//bag012.outassign(output,'bag01.out');rewrite(output);readln(m,n);fori:=1tondoread(weight[i]);readln;fori:=1tondoread(cost[i]);readln;fillchar(f,sizeof(f),0);fori:=1tomdof[0,i]:=0;fori:=1tondof[i,0]:=0;fori:=1tondoforj:=mdownto1dobeginifj-weight[i]>=0thenbeginiff[i-1,j]>f[i-1,j-weight[i]]+cost[i]thenbeginf[i,j]:=f[i-1,j];ff[i,j]:=1;endelsebeginf[i,j]:=f[i-1,j-weight[i]]+cost[i];ff[i,j]:=2;endendelsebeginf[i,j]:=f[i-1,j];ff[i,j]:=1;endend;writeln(f[n,m]);os(n,m);close(input);close(output);end.

k:=0;fori:=ndownto1doforj:=1tomdoif(ff[i,j]=1)and(f[i,j]=max)thenbegininc(k);p[k]:=i;max:=max-c[i];break;end;fori:=kdownto2dowrite(p[i],'');write(p[1]);動態(tài)規(guī)劃-king數(shù)字三角形（IOI’94）如下所示一個數(shù)字三角形738810274445265寫一個程序計算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字和最大每一步可沿直向下或右斜線向下走1<三角形行數(shù)<=100三角形中的數(shù)字為整數(shù)0，1，，，99動態(tài)規(guī)劃-king數(shù)字三角形（IOI’94）輸入：第一行為一個自然數(shù)，表示數(shù)字三角形的行數(shù)n，接下來的n行表示一個數(shù)字三角形輸出：一行一個整數(shù)表示最大和5738810274445265輸出：30動態(tài)規(guī)劃-king分析假設(shè)從頂至數(shù)字三角形的某一位置的所有路徑中，所經(jīng)過的數(shù)字總和最大的那條路徑我們稱之為該位置的最大路徑，由于問題規(guī)定每一步只能沿直線或右斜線向下走，若要走過某一位置，則其前一位置必為其正上方或左上方兩個位置之一。由此可知，當(dāng)前位置的最優(yōu)路徑必定與其左上方或正上方兩個位置的最優(yōu)路徑有關(guān)，且來自其中最優(yōu)的一個我們用一個兩維數(shù)組a記錄三角形中的數(shù)a[I,j]表示數(shù)字三角形的第I行第j列的數(shù)，再用一個兩維數(shù)組maxsum記錄每個位置的最優(yōu)路徑的數(shù)字和。計算maxsum數(shù)組可以用逐行遞推的方法實現(xiàn)（像楊輝三角）動態(tài)規(guī)劃-king分析按三角形的行劃分階段，若行數(shù)為n，則可把問題看做一個n-1個階段的決策問題。先求出第n-1階段(第n-1行上各點)到第n行的的最大和，再依次求出第n-2階段、第n-3階段……第1階段(起始點)各決策點至第n行的最佳路徑。

設(shè)：f[i,j]為從第i階段中的點j至第n行的最大的數(shù)字和；

則:f[n,j]=a[n,j]

1<=j<=n

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}

1<=j<=i.

f[1,1]即為所求。動態(tài)規(guī)劃-king動態(tài)規(guī)劃的基本思想最優(yōu)子結(jié)構(gòu)用動態(tài)程序設(shè)計方法來解決一個問題的第一步是規(guī)劃一個最優(yōu)解的結(jié)構(gòu)。我們說一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，如果該問題的最優(yōu)解中包含了一個或多個子問題的最優(yōu)解，當(dāng)一個問題呈現(xiàn)出最優(yōu)子結(jié)構(gòu)時，動態(tài)程序設(shè)計可能就是一個合適的候選方法了。動態(tài)規(guī)劃-king動態(tài)規(guī)劃的基本思想如數(shù)字三角形就有最優(yōu)子結(jié)構(gòu)當(dāng)前位置的最優(yōu)路徑必定與其左上方或正上方的兩個位置的最優(yōu)路徑有關(guān)，且來自其中最優(yōu)的一個，即問題的最優(yōu)解包含了其中一個子問題的最優(yōu)解如果將問題稍微改變：將三角形中的數(shù)字改為-100~100之間的整數(shù)，計算從頂至底的某處的一條路徑，使路徑經(jīng)過的數(shù)字綜合最接近零，這個問題就不具備最優(yōu)子結(jié)構(gòu)性質(zhì)，因為子問題最優(yōu)反而可能造成問題的解原離零動態(tài)規(guī)劃-king動態(tài)規(guī)劃的基本思想重疊子問題子問題的空間要較小，也就是用來解原問題的一個遞歸算法可反復(fù)解同樣的子問題，而不是總是產(chǎn)生新的子問題，即子問題的總數(shù)是問題規(guī)模的一個多項式。當(dāng)一個遞歸算法不斷地遇到同一問題時，我們說該最優(yōu)化問題包含有重疊子問題相反地，使用分治法解決的問題往往在遞歸的每一步都產(chǎn)生出全新的問題來，如快速排序算法。動態(tài)總是充分使用重疊子問題，對每個子問題只解一次，把解放在一個數(shù)組中，需要時查看。動態(tài)規(guī)劃-king動態(tài)規(guī)劃的基本思想無后效性“過去的歷史只能通過當(dāng)前狀態(tài)去影響它未來的發(fā)展，當(dāng)前的狀態(tài)是對以往歷史的一個總結(jié)”，這種特性稱為無后效性，是多階段決策最優(yōu)化問題的特征。

動態(tài)規(guī)劃-king想要掌握好動態(tài)規(guī)劃，首先要明白幾個概念：階段、狀態(tài)、決策、策略、指標(biāo)函數(shù)。

1．階段：把所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量。

2．狀態(tài)：狀態(tài)表示每個階段開始所處的自然狀況和客觀條件，它描述了研究問題過程中的狀況，又稱不可控因素。

3．決策：決策表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策，在最優(yōu)控制中也稱為控制。描述決策的變量，稱為決策變量。

4．策略：由所有階段的決策組成的決策函數(shù)序列稱為全過程策略，簡稱策略。

5．狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。

6．指標(biāo)函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)。指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。

動態(tài)規(guī)劃-king動態(tài)規(guī)劃算法的基本步驟如果碰到一個問題，能夠滿足以上兩個條件的話，那么就可以去進一步考慮如何去設(shè)計使用動態(tài)規(guī)劃：

（1）劃分階段。把一個問題劃分成為許多階段來思考

（2）設(shè)計合適的狀態(tài)變量(用以遞推的角度)

（3）建立狀態(tài)轉(zhuǎn)移方程(遞推公式)

（4）尋找邊界條件(已知的起始條件)

如果以上幾個步驟都成功完成的話，我們就可以進行編程了。

動態(tài)規(guī)劃-king最長不下降子序列設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為:

a(1)、a(2)、……、a(n)且a(i)<>a(j)

(i<>j)

例如3，18，7，14，10，12，23，41，16，24。

若存在i1<i2<i3<…<ie且有a(i1)<a(i2)<…<a(ie)則稱為長度為e的不下降序列。如上例中3，18，23，24就是一個長度為4的不下降序列，同時也有3，7，10，12，16，24長度為6的不下降序列。程序要求，當(dāng)原數(shù)列給出之后，求出最長的不下降序列。

動態(tài)規(guī)劃-king算法分析根據(jù)動態(tài)規(guī)劃的原理，由后往前進行搜索。

1·對a(n)來說，由于它是最后一個數(shù)，所以當(dāng)從a(n)開始查找時，只存在長度為1的不下降序列；

2·若從a(n-1)開始查找，則存在下面的兩種可能性：

①若a(n-1)<a(n)則存在長度為2的不下降序列a(n-1)，a(n)。

②若a(n-1)>a(n)則存在長度為1的不下降序列a(n-1)或a(n)。

3·

一般若從a(i)開始，此時最長不下降序列應(yīng)該按下列方法求出:

在a(i+1),a(i+2),…,a(n)中，找出一個比a(i)大的且最長的不下降序列，作為它的后繼。4.用數(shù)組b(i),c(i)分別記錄點i到n的最長的不降子序列的長度和點i后繼節(jié)點的編號狀態(tài)轉(zhuǎn)移方程：f(i)=max{f(j)+1}1<=j<I,b[j]<b[i]動態(tài)規(guī)劃-king最長不下降序列拓展一求序列中最長不下降序列的個數(shù)設(shè)t(i)為前i個數(shù)中最長不下降序列的個數(shù),則t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)+1)初始為t(i)=1當(dāng)f(i)=n時，將t(i)累加舉例：1234658109

f:123455677t:111111222答案：f=7時，邊界為∑t=4動態(tài)規(guī)劃-king最長不下降序列拓展二求本質(zhì)不同的最長不下降序列個數(shù)有多少個？如：1234658109有，12346810,12345810,1234689,1234589都是本質(zhì)不同的。但對于1223354

f1223344t1112244

答案有8個，其中4個1235，4個1234t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)+1，bj<>bk,1<=k<j)動態(tài)規(guī)劃-king最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=<x1,x2….xm>,則另一序列Z=<z1,z2,….zk>是X的子序列是指存在一個嚴(yán)格遞增的下標(biāo)序列<i1,i2,….ik>,使得對于所有j=1,2,….k有：

Xij=Zj動態(tài)規(guī)劃-king例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相應(yīng)的遞增下標(biāo)序列為<2,3,5,7>。給定兩個序列X和Y，當(dāng)另一序列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的一個最長公共子序列動態(tài)規(guī)劃-king給定兩個序列X=<x1,x2,….xm>和Y=<y1,y2,…yn>,要求找出X和Y的一個最長公共子序列輸入：輸入文件共有兩行，每行為一個由大寫字母構(gòu)成的長度不超過200的字符串。表示序列X和Y。輸出輸出文件第一行為一個非負(fù)整數(shù)，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出文件僅有一行輸出一個整數(shù)0，否則在輸出文件的第二行輸出所求得的最長公共子序列（也用一個大寫字母組成的字符串表示），若符合條件的最長公共子序列不止一個，只需要輸出其中任意一個。動態(tài)規(guī)劃-king樣例輸入

ABCBDABBDCABA樣例輸出4

BCBA動態(tài)規(guī)劃-kingC[I,j]=0當(dāng)I=0或j=0C[I-1,j-1]+1當(dāng)I,j>=且xi=yjMax(c[I-1,j],c[I,j-1])當(dāng)I,j>0且xi<>yj動態(tài)規(guī)劃-king若輸出所有公共子序列呢？右邊方法的效率不高，但可以實現(xiàn)。只輸出一個公共序列：procedurelcs(i,j:longint);beginif(i=0)or(j=0)thenexit;ifd[i,j]=1thenbeginlcs(i-1,j-1);write(a[i],'');endelseifd[i,j]=2thenlcs(i-1,j)elselcs(i,j-1);end;procedureprint;vari,j,k:longint;flag:boolean;begingt[p]:='';fori:=1tomaxdogt[p]:=gt[p]+gg[i];flag:=true;fori:=1top-1doifgt[p]=gt[i]thenbeginflag:=false;break;end;ifflagtheninc(p);end;procedurelcs(k,i,j:longint);beginifk=0thenbeginprint;exit;end;if(i=0)or(j=0)thenbeginexit;end;ifd[i,j]=1thenbegingg[k]:=a[i];lcs(k-1,i-1,j-1);endelseifd[i,j]=2thenlcs(k,i-1,j)elseifd[i,j]=3thenlcs(k,i,j-1)elseifd[i,j]=4thenbeginlcs(k,i-1,j);lcs(k,i,j-1);end;end;動態(tài)規(guī)劃-king攔截導(dǎo)彈（p1078）某國為了防御敵國的導(dǎo)彈襲擊，發(fā)明出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

動態(tài)規(guī)劃-king攔截導(dǎo)彈輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

輸入：38920715530029917015865

輸出：6（最多攔截的導(dǎo)彈）2（最小需要配備的系統(tǒng)）動態(tài)規(guī)劃-king攔截導(dǎo)彈階段i：由右而左計算導(dǎo)彈n‥導(dǎo)彈1中可攔截的最多導(dǎo)彈數(shù)（1≤i≤n）；狀態(tài)B[i]：由于每個階段中僅一個狀態(tài)，因此可通過一重循環(huán)fori:=n-1downto1do枚舉每個階段的狀態(tài)B[i]；決策k：在攔截導(dǎo)彈i之后應(yīng)攔截哪一枚導(dǎo)彈可使得B[i]最大（i+1≤k≤n），動態(tài)規(guī)劃-king算法：這道題就是典型的最長單調(diào)序列和最長單調(diào)序列的覆蓋問題，兩個問題分別求。問題一：求最長單調(diào)序列的長度。我們設(shè)opt[i]表示從A1到Ai的最長單調(diào)序列長度，則：opt[1]=1opt[i]=max{opt[k]+1}(1<=k<i)&(Ak>=Ai)最后輸出opt[n].問題二：最長單調(diào)序列的覆蓋個數(shù)我們可以不斷求出最長單調(diào)序列，把它們從序列集合中刪去，直到集合為空集，在此過程中進行累加。復(fù)雜度：方法的時間復(fù)雜度為o(n^2)，tju1004已經(jīng)可以Accepted，但是如果n>1000000時，速度顯然不如人意。動態(tài)規(guī)劃-king改進：有沒有更好的方法呢？當(dāng)然有！最長單調(diào)序列，顧名思義，單調(diào)的，即：A[k]<=(or>=><)A[i](k<i)于是難道不可以只保存最后一個數(shù)？首先,開一個足夠大的數(shù)組A:array[1..maxn]oflongintA[i]表示長度為i的最長單調(diào)序列的最后一個數(shù)字，程序如下：動態(tài)規(guī)劃-kingproceduremain;var.............beginfillchar(a,sizeof(a),0);ans:=0;{最長單調(diào)序列的長}readln(n);fors:=1tondobeginread(x);l:=1;r:=ans;{左、右范圍}whliel<=rdobegin{二分}m:=(l+r)shr1;ifa[m]<=xthenl:=m+1elser:=m-1;end;ifl>anstheninc(ans);{新建，即長度為ans+1的最長單調(diào)序列出現(xiàn)了！}a[l]:=x;end;end;最長單調(diào)序列的覆蓋個數(shù)也很好求，只要將ifa[m]>=xthenl:=m+1elser:=m-1中的<=轉(zhuǎn)換為>=即可，其它類似。算法的復(fù)雜度顯然降低了！動態(tài)規(guī)劃-king合唱隊形

N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊形。

合唱隊形是指這樣的一種隊形：設(shè)K位同學(xué)從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK，

則他們的身高滿足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任務(wù)是，已知所有N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形。

動態(tài)規(guī)劃-king輸入文件

輸入文件chorus.in的第一行是一個整數(shù)N(2<=N<=100)，表示同學(xué)的總數(shù)。第一行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高(厘米)。

-輸出文件

輸出文件chorus.out包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列。

-樣例輸入

8

186186150200160130197220

-樣例輸出

4

動態(tài)規(guī)劃-king從左到右進行最長不下降子序列從右到左進行最長不上升子序列然后綜合考慮，枚舉二者最大值動態(tài)規(guī)劃-king方格取數(shù)（P1205）設(shè)有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數(shù),而其他的方格中則放入數(shù)字0。如下圖所示（見樣例）：動態(tài)規(guī)劃-king方格取數(shù)某人從圖的左上角的A點出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B點。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字0）。此人從A點到B點共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。

輸入

輸入的第一行為一個整數(shù)N（表示N*N的方格圖），接下來的每行有三個整數(shù)，前兩個表示位置，第三個數(shù)為該位置上所放的數(shù)。一行單獨的0表示輸入結(jié)束。

輸出

只需輸出一個整數(shù)，表示2條路徑上取得的最大的和。動態(tài)規(guī)劃-king方格取數(shù)動態(tài)規(guī)劃-king若只考慮走一次的情況，則是一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃的過程。

根據(jù)走的步數(shù)來分階段

階段：階段1，在位置(1,1)，階段2，位置可能有兩個(1,2)，(2,1)，等。其中的規(guī)律是階段k，可能的位置是(x,k+1-x),(k>=x>=1)

狀態(tài)：每個階段有若干個狀態(tài)，如上所述階段k的狀態(tài)有:(x,k+1-x),(k>=x>=1)。

決策：在每個位置有可能有兩個或一個決策可選擇，即向下或向右走（當(dāng)然不能出界）。

狀態(tài)轉(zhuǎn)移方程：

位置(x,y)的狀態(tài)：S(x,y)=min{s(x-1,y),s(x,y-1)}+格子(x,y)中的數(shù)。動態(tài)規(guī)劃-king現(xiàn)考慮走兩次。

題目中是兩次分開走的，但我們可以看成兩個人同時走。這時依然按照行走的步數(shù)來分類。

這樣的情況下有一個不同的情況是：可能兩個人同時走入同一個格子取數(shù)，這時肯定不能取兩次數(shù)。

兩條路線同時進行的動態(tài)規(guī)劃中，狀態(tài)和決策以及狀態(tài)轉(zhuǎn)方程移要復(fù)雜一些。動態(tài)規(guī)劃-king兩條路線同時進行的動態(tài)規(guī)劃

階段：按所走的步數(shù)來分階段，從左上角走到右下角，共2n-1個步驟，故共2n-1個階段。但，有兩條線路，故每一階段的狀態(tài)都會復(fù)雜一些。

狀態(tài)：有兩線路同時走，在某階段的某狀態(tài)，要用兩個坐標(biāo)來分別表示兩線路的兩個點。如：第一階段，共一個狀態(tài)：(1,1),(1,1)；第二階段，(1,2),(1,2);(1,2),(2,1);(2,1),(1,2);(2,1),(2,1)共四個狀態(tài)。

由于在第k階段的任何兩個點的x,y坐標(biāo)是有關(guān)系的：k+1=x+y。故可只用ｘ坐標(biāo)來表示一點的坐標(biāo)，故狀態(tài)可表示為(x1,x2)，對應(yīng)的y坐標(biāo)為：y1=k+1-x1,y2=k+1-x2。

決策：若用0,1分別表示向下或向右走，則每個狀態(tài)的可能決策有四種：(1,1),(0,0),(1,0),(0,1)。兩個數(shù)值分別表示兩個點的下一步走向。

狀態(tài)轉(zhuǎn)移方程：

設(shè)map(x,y)為方格圖，f(k,x1,x2)表示第k個階段走到(x1,x2)狀態(tài)的最大和

f(1,1,1)＝map(x1,1+1-x1)即map(1,1)

f(k,x1,x2)=max{f(k-1,x1',x2')+map(x1,y1)｜x1=x2，

f(k-1,x1',x2')+map(x1,y1)＋map(x2,y2)｜x1<>x2}

(x1',x2')表示可通過某決策到達(dá)(x1,x2)的所有點動態(tài)規(guī)劃-king記憶化搜索方式解決動規(guī)functionfind(i,x1,x2:longint):longint;varg,h,t1:longint;beginif(i=1)and(x1=1)and(x2=1)thenbeginf[1,1,1]:=map[1,1];find:=f[1,1,1];vis[1,1,1]:=false;exit;end;if(x1=0)or(x2=0)or(i+1-x1=0)or(i+1-x2=0)thenbeginfind:=f[i,x1,x2];exit;end;ifnotvis[i,x1,x2]thenbeginfind:=f[i,x1,x2];exit;end;t1:=0;ifx1=x2thenbeginforg:=0to1doforh:=0to1dobeginift1<find(i-1,x1-g,x2-h)+map[x1,i+1-x1]thent1:=find(i-1,x1-g,x2-h)+map[x1,i+1-x1];end;endelsebeginforg:=0to1doforh:=0to1doift1<find(i-1,x1-g,x2-h)+map[x1,i+1-x1]+map[x2,i+1-x2]thent1:=find(i-1,x1-g,x2-h)+map[x1,i+1-x1]+map[x2,i+1-x2];end;f[i,x1,x2]:=t1;find:=t1;vis[i,x1,x2]:=false;end;動態(tài)規(guī)劃-king數(shù)字最大乘積在數(shù)字串中插入若干(K個)乘號使總的乘積最大。分析：定義從l到r加入k個乘號的最大乘積值為p(l,r,k)。動態(tài)規(guī)劃-king解題思路

定義:從l到r加入k個乘號的最大乘積值p(l,r,k)。p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}動態(tài)規(guī)劃-king機器生產(chǎn)某工廠購進1000臺機器，準(zhǔn)備生產(chǎn)P1和P2兩種產(chǎn)品。若生產(chǎn)產(chǎn)品P1，每臺機器每年可收入4500元，但機器損壞率達(dá)65%。若生產(chǎn)產(chǎn)品P2，每臺機器每年可收入3500元，但損壞率僅有35%。三年后機器全部淘汰，購入新機器。應(yīng)該如何安排生產(chǎn)（計劃以一年為周期），使三年收入最多？動態(tài)規(guī)劃-king分析：假設(shè)X1、Y1表示第一年時生產(chǎn)P1的機器臺數(shù)和生產(chǎn)P2的機器臺數(shù)，則X2，Y2，X3，Y3以此類推?？芍?/p>

X1+Y1=1000 X2+Y2=0.35*X1+0.65*Y1 X3+Y3=0.35*X2+0.65*Y2而三年的總收入為：Z=4500*（X1+X2+X3）+3500*（Y1+Y2+Y3）（1）設(shè)在第二年后還剩N臺機器，則第三年的收入為：

Z(3,N) =4500*X3+3500*Y3 =4500*X3+3500*（N-X3） =1000*X3+3500N

顯然我們知道：0<=X3<=N，則Z3最大時，X3=N（Y3=0），此時，Zmax(3，N)=4500*N。（2）設(shè)在第一年后還剩N臺機器，則第二年后（最后兩年）的收入為：

Z（2，N）=4500*X2+3500*（N-X2）+Zmax(3,0.35*X2+0.65*(N-X2)) =1000*X2+3500*N+4500*（0.65*N-0.3*X2） =（3500+2925）*N-（1350-1000）*X2 <=6425*N

顯然，當(dāng)X2=0，X3=0.65*N時，Z（2，N）取最大值

動態(tài)規(guī)劃-king（3）最后考慮整個三年的生產(chǎn)，設(shè)開始時有N臺機器，則三年的收入總和為：

Z（1，N）=4500*X1+3500（N-X1）+Zmax(2，0.35*X1+0.65*(N-X1)) =1000*X1+3500*N+6425*（0.65*N-0.3*X1） =（3500+6425*0.65）*N-（0.3*6425-1000）*X1 <=（3500+6425*0.65）*N

綜上所述，當(dāng)X1=0，X2=0，X3=0.65*0.65*N時，收入取得最大值。即： 生產(chǎn)P1的機器臺數(shù) 生產(chǎn)P2的機器臺數(shù)第1年 0 1000第2年 0 650第3年 422 0此時三年收入最大。動態(tài)規(guī)劃-kingMOD4余數(shù)最小問題如圖，已知一個有向圖，求一條從最左邊的點走到最右邊點的方案（只能從左往右走），使得所經(jīng)過的權(quán)值和除以4的余數(shù)最小。動態(tài)規(guī)劃-king

設(shè)所有點從左至右編號為1…4，MIN（i）表示前I個點的最優(yōu)值，很容易得出一個方程：

Min(i)=min{(Min(I-1)+num[I-1,1])mod4,Min(I-1)+num[I-1,2])mod4}

通過這個方程可以求出一條路徑為（2+3+1）MOD4=2但最優(yōu)值實際上是（2+1+1）MOD4=0。

為什么會出錯呢？分析動態(tài)規(guī)劃-king

觀察以上數(shù)據(jù)發(fā)現(xiàn)取Min(３)的時候，動態(tài)規(guī)劃求出來的最優(yōu)值為１，而正確的值應(yīng)該為0，由此可知本題對應(yīng)于一條最優(yōu)路徑，并不是這條路徑上的所有點的最優(yōu)值都是從點１到該點可得的最優(yōu)值，對于每一個階段都取最優(yōu)值并不能保證求出最優(yōu)解，即不滿足最優(yōu)化原理，因此這種規(guī)劃方法在本題行不通。動態(tài)規(guī)劃-king讓我們來換一個思路思考本題，因為本題是要求總和除以４余數(shù)最小的一條路徑，我們先撇開最小余數(shù)不去管它，而是將本題改為從點1到點４的所有路徑中，求出每條路上權(quán)值和除以４的不同余數(shù)的個數(shù)。我們設(shè)一個數(shù)組can[I,j]表示從點1至點Ｉ可不可以求出一條路徑是該路徑的權(quán)值總和除以４的余數(shù)為Ｊ，那么又可以得出一個方程：

can[I,j]:=can[I-1,k]and((k+num[I,p])mod4=j)(0<=k<=3,1<=p<=2)can[1,0]=truecan[1,1]=falsecan[1,2]=falsecan[1,3]=false

通過這個方程我們可以求出從點1至點Ｉ可以達(dá)到的所有余數(shù)，我們只要從這些余數(shù)中選出一個值最小的輸出就行。動態(tài)規(guī)劃-king線性規(guī)劃模型

例1：機器分配問題?？偣緭碛懈咝a(chǎn)設(shè)備M臺，準(zhǔn)備分給下屬的N個公司。各分公司若獲得這些設(shè)備，可以為國家提供一定的盈利。問：如何分配這M臺設(shè)備才能使國家得到的盈利最大？求出最大盈利值。其中M<=150，N<=100。分配原則：每個公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺數(shù)不得超過總設(shè)備數(shù)M。數(shù)據(jù)文件格式為：第一行保存兩個數(shù)，第一個數(shù)是設(shè)備臺數(shù)M，第二個數(shù)是分公司數(shù)N。接下來是一個N*M的矩陣，表明了第I個公司分配J臺機器的盈利。

動態(tài)規(guī)劃-king分析用機器數(shù)來做狀態(tài)，數(shù)組F[I，J]表示前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時間復(fù)雜度O(N*M2)動態(tài)規(guī)劃-king有一條河從東向西將某地區(qū)分為南北2個部分。河的兩岸各有N個城市。北岸的每個城市都與南岸的某個城市是友好城市，而且關(guān)系是一一對應(yīng)的?，F(xiàn)在要求在2個友好城市之間建立一條航線，但由于天氣的緣故，所有的航線都不能相交，因此，就不能給所有的友好城市建立友好航線。請設(shè)計一個修建航線的方案，能建最多的航線而且不相交。輸入：第一行為一個正整數(shù)N(N<=1000)以下N行，記第i行有一個正整數(shù)j，表示北岸的城市i與南岸的城市j互為友好城市。其中城市編號是按從東到西排列的。輸出：僅一行，即最多的航線數(shù)。

船(ceoi)動態(tài)規(guī)劃-king

首先我們需要判定對于給定的兩條航線是否相交，設(shè)北岸城市i1，j1(i1<j1)分別與南岸城市i2，j2互為友好城市，那么這兩條航線不相交(以下簡稱為i1，j1相容)的充要條件是I2<=J2。(結(jié)論1)由下圖就可以很容易地得到這個結(jié)論。

i1j2i2j1j2i2j1i1北岸：

南岸：

圖

一

圖

二

分析動態(tài)規(guī)劃-king

從上面的結(jié)論可以看出，最優(yōu)的選擇方案中，如果將所有航線按北岸村莊號從小到大排序，序列中每一個北岸村莊對應(yīng)的南岸村莊號必然滿足B1<B2<B3……<Bn（n為選出來的航線數(shù)）。同樣，對于任一個方案，如果北岸村莊排好序后，與之對應(yīng)的南岸村莊也是按升序排列，那么該方案必然不存在相交的兩條航線；相反，如果南岸村莊不是按升序排列，必存在兩條相交的航線。因此，我們可以先將各航線按北岸村莊號排一個序，那么最優(yōu)的方案必然是從相對應(yīng)的南岸村莊中找出一個最長不下降序列，該序列的長度即為問題的解。動態(tài)規(guī)劃-king凸多邊形三角劃分

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

第二行N個頂點（從1到N）的權(quán)值輸出格式：最小的和的值各三角形組成的方式輸入示例：5122123245231輸出示例：Theminimumis：12214884Theformationof3triangle:345,153,123動態(tài)規(guī)劃-king分析設(shè)F[I,J]（I<J）表示從頂點I到頂點J的凸多邊形三角剖分后所得到的最大乘積，我們可以得到下面的動態(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ù)較大時有可能超過長整形范圍，所以還需用高精度計算

動態(tài)規(guī)劃-king動態(tài)規(guī)劃-king堆塔問題

設(shè)有n個邊長為1的正立方體，在一個寬為1的軌道上堆塔，但塔本身不能分離。

例如n=1時，只有1種方案□

n=2時，有2種方案

堆塔的規(guī)則為底層必須有支撐，如下列的堆法是合法的：

下面的堆法是不合法的：

程序要求：輸入n(n<=40)，求出

動態(tài)規(guī)劃-king程序要求：輸入n(n<=40)，求出

①總共有多少種不同的方案

②堆成每層的方案數(shù)是多少，例如n=6時，堆成1層的方案數(shù)為1，……堆成6層的方案數(shù)為1……

動態(tài)規(guī)劃-king分析問題①的分析不再重復(fù)

關(guān)于問題②，可以這樣考慮，將n個立方體的第一列去掉的話，則成為一個比n小的堆塔問題，這樣問題②就可以用動態(tài)規(guī)劃法來解。具體方法是從1到n依次求出堆成每層的方案數(shù)，設(shè)f(n,k)為堆成k層的方案數(shù)，則遞推公式為：

[算法設(shè)計]

由于n最大可達(dá)到40，所以堆塔的總方案數(shù)超過了長整形數(shù)的范圍，程序采用了高精度加法運算。

動態(tài)規(guī)劃-king矩陣乘法一個a*b的矩陣和一個b*c的矩陣相乘需要a*b*c次乘法，得到一個a*c的矩陣?，F(xiàn)在給你一系列矩陣的連乘式，求最少的乘法次數(shù)。子結(jié)構(gòu)劃分：中分?？紤]最后兩個矩陣相乘。這兩個矩陣必定對應(yīng)某一個劃分，由左右兩部分分別計算得到。最優(yōu)子結(jié)構(gòu)？無后效性？動態(tài)規(guī)劃-king動態(tài)規(guī)劃方程變量的定義：ri::=第i個矩陣的行數(shù)ci::=第i個矩陣的列數(shù)fij::=將第i-j個矩陣相乘所需的最少乘法次數(shù)方程：fij=min{fik+fk+1j}+ri*ck*cji<=k<=jfii=0Answer=f1n動態(tài)規(guī)劃-king取數(shù)游戲有n個數(shù)a1、a2、…、an。每次從中刪去一個數(shù)，規(guī)定最左最右兩個數(shù)不能刪除。這樣共進行n-2次，求得分最高的方案。計分方式：設(shè)某一次刪除的數(shù)為ai，則你的得分為ai-1*ai*ai+1。所有得分相加即為最后總分。動態(tài)規(guī)劃-king動態(tài)規(guī)劃方程變量的定義：fij::=第i-j個數(shù)所能得到的最高得分方程：fij=max{fik+fkj}+ai*ak*aj1<=i<k<j<=Nfii+1=0Answer=f1n動態(tài)規(guī)劃-king01背包問題一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價值。

動態(tài)規(guī)劃-king分析顯然這個題可用深度優(yōu)先方法對每件物品進行枚舉(選或不選用0,1控制).程序簡單,但是當(dāng)n的值很大的時候不能滿足時間要求，時間復(fù)雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數(shù)設(shè)f(i，x)表示前i件物品，總重量不超過x的最優(yōu)價值則f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））f（n，m）即為最優(yōu)解，邊界條件為f（0，x）＝0

，f(i,0)=0;動態(tài)規(guī)劃-king完全背包問題設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi公斤，每件價值ci元。現(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。

動態(tài)規(guī)劃-king問題分析動態(tài)規(guī)劃-king排隊買票問題一場演唱會即將舉行?，F(xiàn)有n個歌迷排隊買票，一個人買一張，而售票處規(guī)定，一個人每次最多只能買兩張票。假設(shè)第i位歌迷買一張票需要時間Ti（1≤i≤n），隊伍中相鄰的兩位歌迷（第j個人和第j+1個人）也可以由其中一個人買兩張票，而另一位就可以不用排隊了，則這兩位歌迷買兩張票的時間變?yōu)镽j，假如Rj〈Tj+Tj+1，這樣做就可以縮短后面歌迷等待的時間，加快整個售票的進程。現(xiàn)給出n,Tj和Rj，求使每個人都買到票的最短時間和方法。動態(tài)規(guī)劃-king最優(yōu)子結(jié)構(gòu)性質(zhì):在最優(yōu)策略中，任意m個連續(xù)的決策也肯定是最優(yōu)的,即問題的最優(yōu)解包含子問題的最優(yōu)解。無后效性：要使前i個人買票時間最短，只需考慮前i個人的買票方式，與隊列以后的人無關(guān)。

動態(tài)規(guī)劃-king遞歸方程令f[i]表示到第i個人為止所需的最短時間，則數(shù)據(jù)結(jié)構(gòu)用一個數(shù)組f[]表示到第i個人為止所需的最短時間源代碼

動態(tài)規(guī)劃-king程序?qū)崿F(xiàn)BUY-TICKS(T,R)

n←length[T]f[0]←0

f[1]←T[1]forl←2ton

do

f[i]←f[i-2]+R[i-1]iff[i]

>f[i-1]+T[i]thenf[i]←f[i-1]+T[i]returnf動態(tài)規(guī)劃-king機器分配

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

動態(tài)規(guī)劃-king分析用機器數(shù)來做狀態(tài)，數(shù)組F[I，J]表示前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時間復(fù)雜度O(N*M2)動態(tài)規(guī)劃-king凸多邊形三角劃分

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

第二行N個頂點（從1到N）的權(quán)值輸出格式：最小的和的值各三角形組成的方式輸入示例：5122123245231輸出示例：Theminimumis：12214884Theformationof3triangle:345,153,123動態(tài)規(guī)劃-king分析設(shè)F[I,J]（I<J）表示從頂點I到頂點J的凸多邊形三角剖分后所得到的最大乘積，我們可以得到下面的動態(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ù)較大時有可能超過長整形范圍，所以還需用高精度計算

動態(tài)規(guī)劃-king系統(tǒng)可靠性

一個系統(tǒng)由若干部件串聯(lián)而成，只要有一個部件故障，系統(tǒng)就不能正常運行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，備用件就自動進入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？給定一些系統(tǒng)備用件的單價Ck，以及當(dāng)用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]）動態(tài)規(guī)劃-king分析例：輸入：220 30.60.650.70.750.80.850.950.70.750.80.80.90.95輸出：0.6375設(shè)F[I,money]表示將money的資金用到前I項備用件中去的最大可靠性，則有

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動態(tài)規(guī)劃-king快餐問題

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

動態(tài)規(guī)劃-king分析本題是一個非常典型的資源分配問題。由于每條生產(chǎn)線的生產(chǎn)是相互獨立，不互相影響的，所以此題可以以生產(chǎn)線為階段用動態(tài)規(guī)劃求解。狀態(tài)表示：用p[i,j,k]表示前i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)飲料的個數(shù)。用r[i,j,k]表示第i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)飲料的個數(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)時間)r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的時間復(fù)雜度為O(N*1004),動態(tài)規(guī)劃-king優(yōu)化在本題中，可以在動態(tài)規(guī)劃方法中加入了貪心算法思想：即首先計算出每天生產(chǎn)套數(shù)的上限值（由A,B,C計算，即min｛100divA，100divB，100divc｝），接著，用貪心法計算出這N條流水線可以生產(chǎn)的套數(shù)，并與上限比較，大于則輸出上限值并退出，否則再調(diào)用動態(tài)規(guī)劃；同時，在運行動態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進行比較，這樣以來，便可望在動態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計為：S1：讀入數(shù)據(jù)。S2：貪心求上限并計算出一可行解，判斷是否需進行下一步。S3：動態(tài)規(guī)劃求解。S4：輸出。動態(tài)規(guī)劃-king其他優(yōu)化方法1.存儲結(jié)構(gòu)：由于每一階段狀態(tài)只與上一階段狀態(tài)有關(guān)，所以我們可以只用兩個100*100的數(shù)組滾動實現(xiàn)。但考慮到滾動是有大量的賦值，可以改進為動態(tài)數(shù)組，每次交換時只需交換指針即可，這樣比原來數(shù)組間賦值要快。2.減少循環(huán)次數(shù)：在計算每一階段狀態(tài)過程中無疑要用到4重循環(huán)，我們可以這樣修改每一重循環(huán)的起始值和終數(shù)，其中q1,q2為A，B上限值。原起始值改進后的起始值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動態(tài)規(guī)劃-king石子合并在一園形操場四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(≤20), (1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少(2)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大輸入數(shù)據(jù): 第一行為石子堆數(shù)N;

第二行為每堆石子數(shù),每兩個數(shù)之間用一空格分隔.輸出數(shù)據(jù): 從第1至第N行為得分最小的合并方案.第N+1行為空行.從N+2到2N+1行是得分最大的合并方案.動態(tài)規(guī)劃-king示例動態(tài)規(guī)劃-king貪心法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顯然，貪心法是錯誤的。動態(tài)規(guī)劃-king動態(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這樣，我們完美地解決了這道題。時間復(fù)雜度也是O(n2)。動態(tài)規(guī)劃-king積木游戲一種積木游戲，游戲者有N塊編號依次為1，2，…，N的長方體積木。第I塊積木通過同一頂點三條邊的長度分別為ai,bi,ci（i=1,2,…,N），1從N塊積木中選出若干塊，并將他們摞成M（1<=M<=N）根柱子，編號依次為1,2,…,M，要求第k根柱子的任意一塊積木的編號都必須大于第K-1根柱子任意一塊積木的編號（2<=K<=M）。2對于每一根柱子，一定要滿足下面三個條件：除最頂上的一塊積木外，任意一塊積木的上表面同且僅同另一塊積木的下表面接觸；對于任意兩塊上下表面相接觸的積木，若m,n是下面一塊積木接觸面的兩條邊（m>=n），x,y是上面一塊積木接觸面的兩條邊（x>=y），則一定滿足m.>=x和n>=y；下面的積木的編號要小于上面的積木的編號。請你編一程序，尋找一種游戲方案，使得所有能摞成的M根柱子的高度之和最大。動態(tài)規(guī)劃-king積木游戲輸入數(shù)據(jù)：文件的第一行是兩個正整數(shù)N和M（1<=M<=N<=100）,分別表示積木總數(shù)和要求摞成的柱子數(shù)。這兩個數(shù)之間用一個空格符隔開。接下來的N行是編號從1到N個積木的尺寸，每行有三個1至500之間的整數(shù)，分別表示該積木三條邊的長度。同一行相鄰兩個數(shù)之間用一個空格符隔開。輸出數(shù)據(jù)：文件只有一行，是一個整數(shù)，表示所求得的游戲方案中M根柱子的高度之和動態(tài)規(guī)劃-king分析設(shè)（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]表示當(dāng)把第i塊積木的第j面朝上時所對應(yīng)的高，即所增加的高度；（3）can[i,k,p,kc]表示第I塊積木以其第k面朝上，第p塊積木以第kc面朝上時，能否將積木I放在積木p的上面。1表示能，0表示不能。對于f[i,j,k],有兩種可能：1.除去第I塊積木，第j根柱子的最上面的積木為編號為p的，若第p塊積木以第kc面朝上，必須保證當(dāng)?shù)贗塊積木以k面朝上時能夠被放在上面，即can[i,k,p,kc]=1；2.第i塊積木是第j根柱子的第一塊積木，第j-1根柱子的最上面為第p塊積木，則此時第p塊積木可以以任意一面朝上。則有：動態(tài)規(guī)劃-king動態(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);時間復(fù)雜度為O(n^2*m)動態(tài)規(guī)劃-king免費餡餅SERKOI最新推出了一種叫做“免費餡餅”的游戲。游戲在一個舞臺上進行。舞臺的寬度為W格，天幕的高度為H格，游戲者占一格。開始時，游戲者站在舞臺的正中央，手里拿著一個托盤。游戲開始后，從舞臺天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動去接餡餅。游戲者每秒可以向左或右移動一格或兩格，也可以站在愿地不動。餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就收集到了這塊餡餅。寫一個程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分?jǐn)?shù)之和最大。動態(tài)規(guī)劃-king免費餡餅輸入數(shù)據(jù)：輸入文件的第一行是用空格分開的兩個正整數(shù)，分別給出了舞臺的寬度W（1~99之間的奇數(shù)）和高度H（1~100之間的整數(shù)）。接下來依餡餅的初始下落時間順序給出了一塊餡餅信息。由四個正整數(shù)組成，分別表示了餡餅的初始下落時刻（0~1000秒），水平位置、下落速度（1~100）以及分值。游戲開始時刻為0。從1開始自左向右依次對水平方向的每格編號。輸出數(shù)據(jù)：輸出文件的第一行給出了一個正整數(shù)，表示你的程序所收集到的最大分?jǐn)?shù)之和。動態(tài)規(guī)劃-king分析我們將問題中的餡餅信息用一個表格存儲。表格的第I行第J列表示的是游戲者在第I秒到達(dá)第J列所能取得的分值。那么問題便變成了一個類似數(shù)字三角形的問題：從表格的第一行開始往下走，每次只能向左或右移動一格或兩格，或不移動走到下一行。怎樣走才能得到最大的分值。因此，我們很容易想到用動態(tài)規(guī)劃求解。F[I,J]表示游戲進行到第I秒，這時游戲者站在第J列時所能得到的最大分值。那么動態(tài)轉(zhuǎn)移方程為：

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