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

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

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

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

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

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

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

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

動(dòng)態(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；動(dòng)態(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；

動(dòng)態(tài)規(guī)劃-king動(dòng)態(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）表示點(diǎn)x到v10的最短路徑長(zhǎng)度則f(10)=0

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

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

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

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

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

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

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

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

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

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

（1）劃分階段。把一個(gè)問(wèn)題劃分成為許多階段來(lái)思考

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

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

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

如果以上幾個(gè)步驟都成功完成的話，我們就可以進(jìn)行編程了。

動(dòng)態(tài)規(guī)劃-king最長(zhǎng)不下降子序列設(shè)有由n個(gè)不相同的整數(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)則稱為長(zhǎng)度為e的不下降序列。如上例中3，18，23，24就是一個(gè)長(zhǎng)度為4的不下降序列，同時(shí)也有3，7，10，12，16，24長(zhǎng)度為6的不下降序列。程序要求，當(dāng)原數(shù)列給出之后，求出最長(zhǎng)的不下降序列。

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

1·對(duì)a(n)來(lái)說(shuō)，由于它是最后一個(gè)數(shù)，所以當(dāng)從a(n)開始查找時(shí)，只存在長(zhǎng)度為1的不下降序列；

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

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

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

3·

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

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

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

f1223344t1112244

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

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

ABCBDABBDCABA樣例輸出4

BCBA動(dòng)態(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動(dòng)態(tài)規(guī)劃-king若輸出所有公共子序列呢？右邊方法的效率不高，但可以實(shí)現(xiàn)。只輸出一個(gè)公共序列：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;動(dòng)態(tài)規(guī)劃-king攔截導(dǎo)彈（p1078）某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)明出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

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

輸入：38920715530029917015865

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

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

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

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

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

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

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

-輸出文件

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

-樣例輸入

8

186186150200160130197220

-樣例輸出

4

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

輸入

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

輸出

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

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

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

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

決策：在每個(gè)位置有可能有兩個(gè)或一個(gè)決策可選擇，即向下或向右走（當(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ù)。動(dòng)態(tài)規(guī)劃-king現(xiàn)考慮走兩次。

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

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

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

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

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

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

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

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

設(shè)map(x,y)為方格圖，f(k,x1,x2)表示第k個(gè)階段走到(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')表示可通過(guò)某決策到達(dá)(x1,x2)的所有點(diǎn)動(dòng)態(tài)規(guī)劃-king記憶化搜索方式解決動(dòng)規(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;動(dòng)態(tài)規(guī)劃-king數(shù)字最大乘積在數(shù)字串中插入若干(K個(gè))乘號(hào)使總的乘積最大。分析：定義從l到r加入k個(gè)乘號(hào)的最大乘積值為p(l,r,k)。動(dòng)態(tài)規(guī)劃-king解題思路

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

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

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

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時(shí)，Z（2，N）取最大值

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

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時(shí)，收入取得最大值。即： 生產(chǎn)P1的機(jī)器臺(tái)數(shù) 生產(chǎn)P2的機(jī)器臺(tái)數(shù)第1年 0 1000第2年 0 650第3年 422 0此時(shí)三年收入最大。動(dòng)態(tài)規(guī)劃-kingMOD4余數(shù)最小問(wèn)題如圖，已知一個(gè)有向圖，求一條從最左邊的點(diǎn)走到最右邊點(diǎn)的方案（只能從左往右走），使得所經(jīng)過(guò)的權(quán)值和除以4的余數(shù)最小。動(dòng)態(tài)規(guī)劃-king

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

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

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

為什么會(huì)出錯(cuò)呢？分析動(dòng)態(tài)規(guī)劃-king

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

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

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

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

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

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

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

i1j2i2j1j2i2j1i1北岸：

南岸：

圖

一

圖

二

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

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

給定一個(gè)具有N（N<50）個(gè)頂點(diǎn)（從1到N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問(wèn)如何把這個(gè)凸多邊形劃分成N-2個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之和最?。枯斎胛募旱谝恍许旤c(diǎn)數(shù)N

第二行N個(gè)頂點(diǎn)（從1到N）的權(quán)值輸出格式：最小的和的值各三角形組成的方式輸入示例：5122123245231輸出示例：Theminimumis：12214884Theformationof3triangle:345,153,123動(dòng)態(tài)規(guī)劃-king分析設(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í)有可能超過(guò)長(zhǎng)整形范圍，所以還需用高精度計(jì)算

動(dòng)態(tài)規(guī)劃-king動(dòng)態(tài)規(guī)劃-king堆塔問(wèn)題

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

例如n=1時(shí)，只有1種方案□

n=2時(shí)，有2種方案

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

下面的堆法是不合法的：

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

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

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

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

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

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

[算法設(shè)計(jì)]

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

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

動(dòng)態(tài)規(guī)劃-king分析顯然這個(gè)題可用深度優(yōu)先方法對(duì)每件物品進(jìn)行枚舉(選或不選用0,1控制).程序簡(jiǎn)單,但是當(dāng)n的值很大的時(shí)候不能滿足時(shí)間要求，時(shí)間復(fù)雜度為O（2n）。按遞歸的思想我們可以把問(wèn)題分解為子問(wèn)題,使用遞歸函數(shù)設(shè)f(i，x)表示前i件物品，總重量不超過(guò)x的最優(yōu)價(jià)值則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;動(dòng)態(tài)規(guī)劃-king完全背包問(wèn)題設(shè)有n種物品，每一種物品數(shù)量無(wú)限。第i種物品每件重量為wi公斤，每件價(jià)值ci元。現(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。

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

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

動(dòng)態(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動(dòng)態(tài)規(guī)劃-king機(jī)器分配

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

動(dòng)態(tài)規(guī)劃-king分析用機(jī)器數(shù)來(lái)做狀態(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)動(dòng)態(tài)規(guī)劃-king凸多邊形三角劃分

給定一個(gè)具有N（N<50）個(gè)頂點(diǎn)（從1到N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問(wè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動(dòng)態(tài)規(guī)劃-king分析設(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í)有可能超過(guò)長(zhǎng)整形范圍，所以還需用高精度計(jì)算

動(dòng)態(tài)規(guī)劃-king系統(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]）動(dòng)態(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項(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動(dòng)態(tài)規(guī)劃-king快餐問(wèn)題

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)量。為簡(jiǎn)單起見，假設(shè)漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過(guò)100個(gè)。輸入:第一行為三個(gè)不超過(guò)100的正整數(shù)A、B、C中間以一個(gè)空格分開。第二行為3個(gè)不超過(guò)100的正整數(shù)p1,p2,p3分別為漢堡，薯?xiàng)l和飲料的單位生產(chǎn)耗時(shí)。中間以一個(gè)空格分開。第三行為N(0<=0<=10)，第四行為N個(gè)不超過(guò)10000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時(shí)間，中間以一個(gè)空格分開。輸出:每天套餐的最大產(chǎn)量。

動(dòng)態(tài)規(guī)劃-king分析本題是一個(gè)非常典型的資源分配問(wèn)題。由于每條生產(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),動(dòng)態(tài)規(guī)劃-king優(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ī)劃的過(guò)程中，也可以每完成一階段工作便與上限值進(jìn)行比較，這樣以來(lái)，便可望在動(dòng)態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計(jì)為：S1：讀入數(shù)據(jù)。S2：貪心求上限并計(jì)算出一可行解，判斷是否需進(jìn)行下一步。S3：動(dòng)態(tài)規(guī)劃求解。S4：輸出。動(dòng)態(tài)規(guī)劃-king其他優(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í)只需交換指針即可，這樣比原來(lái)數(shù)組間賦值要快。2.減少循環(huán)次數(shù)：在計(jì)算每一階段狀態(tài)過(guò)程中無(wú)疑要用到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動(dòng)態(tài)規(guī)劃-king石子合并在一園形操場(chǎng)四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(≤20), (1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少(2)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大輸入數(shù)據(jù): 第一行為石子堆數(shù)N;

第二行為每堆石子數(shù),每?jī)蓚€(gè)數(shù)之間用一空格分隔.輸出數(shù)據(jù): 從第1至第N行為得分最小的合并方案.第N+1行為空行.從N+2到2N+1行是得分最大的合并方案.動(dòng)態(tài)規(guī)劃-king示例動(dòng)態(tài)規(guī)劃-king貪心法N=5石子數(shù)分別為346542。用貪心法的合并過(guò)程如下：第一次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ò)誤的。動(dòng)態(tài)規(guī)劃-king動(dòng)態(tài)規(guī)劃用data[i,j]表示將從第i顆石子開始的接下來(lái)j顆石子合并所得的分值，max[i,j]表示將從第i顆石子開始的接下來(lá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顆石子開始的接下來(lá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)。動(dòng)態(tài)規(guī)劃-king積木游戲一種積木游戲，游戲者有N塊編號(hào)依次為1，2，…，N的長(zhǎng)方體積木。第I塊積木通過(guò)同一頂點(diǎn)三條邊的長(zhǎng)度分別為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根柱子的高度之和最大。動(dòng)態(tài)規(guī)劃-king積木游戲輸入數(shù)據(jù)：文件的第一行是兩個(gè)正整數(shù)N和M（1<=M<=N<=100）,分別表示積木總數(shù)和要求摞成的柱子數(shù)。這兩個(gè)數(shù)之間用一個(gè)空格符隔開。接下來(lái)的N行是編號(hào)從1到N個(gè)積木的尺寸，每行有三個(gè)1至500之間的整數(shù)，分別表示該積木三條邊的長(zhǎng)度。同一行相鄰兩個(gè)數(shù)之間用一個(gè)空格符隔開。輸出數(shù)據(jù)：文件只有一行，是一個(gè)整數(shù)，表示所求得的游戲方案中M根柱子的高度之和動(dòng)態(tài)規(guī)劃-king分析設(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塊積木可以以任意一面朝上。則有：動(dòng)態(tài)規(guī)劃-king動(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)動(dòng)態(tài)規(guī)劃-king免費(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ù)之和最大。動(dòng)態(tài)規(guī)劃-king免費(fèi)餡餅輸入數(shù)據(jù)：輸入文件的第一行是用空格分開的兩個(gè)正整數(shù)，分別給出了舞臺(tái)的寬度W（1~99之間的奇數(shù)）和高度H（1~100之間的整數(shù)）。接下來(lái)依餡餅的初始下落時(shí)間順序給出了一塊餡餅信息。由四個(gè)正整數(shù)組成，分別表示了餡餅的初始下落時(shí)刻（0~1000秒），水平位置、下落速度（1~100）以及分值。游戲開始時(shí)刻為0。從1開始自左向右依次對(duì)水平方向的每格編號(hào)。輸出數(shù)據(jù)：輸出文件的第一行給出了一個(gè)正整數(shù)，表示你的程序所收集到的最大分?jǐn)?shù)之和。動(dòng)態(tài)規(guī)劃-king分析我們將問(wèn)題中的餡餅信息用一個(gè)表格存儲(chǔ)。表格的第I行第J列表示的是游戲者在第I秒到達(dá)第J列所能取得的分值。那么問(wèn)題便變成了一個(gè)類似數(shù)字三角形的問(wèn)題：從表格的第一行開始往下走，每次只能向左或右移動(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)動(dòng)態(tài)規(guī)劃-king釘子和小球有一個(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)在的問(wèn)題是計(jì)算拔掉某些釘子后，小球落在編號(hào)為m的格子中的概率pm。假定最下面一排釘子不會(huì)被拔掉。例如圖3是某些釘子被拔掉后小球一條可能的路徑。動(dòng)態(tài)規(guī)劃-king釘子和小球輸入：第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動(dòng)態(tài)規(guī)劃-king分析設(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)