動(dòng)態(tài)規(guī)劃教材

1、動(dòng)態(tài)規(guī)劃一、動(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ī)劃運(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ī)劃是

2、一種方法，是考慮問(wèn)題的一種途徑，而不是一種算法。因此，它 不像深度優(yōu)先和廣度優(yōu)先那樣可以提供一套模式。它必須對(duì)具體問(wèn)題進(jìn)行具體分 析。需要豐富的想象力和創(chuàng)造力去建立模型求解。二、動(dòng)態(tài)規(guī)劃的幾個(gè)基本概念想要掌握好動(dòng)態(tài)規(guī)劃，首先要明白幾個(gè)概念：階段、狀態(tài)、決策、策略、指 標(biāo)函數(shù)。階段：把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿羰畟€(gè)相互聯(lián)系的階段，以便能按一 定的次序去求解。描述階段的變量稱為階段變量。狀態(tài)：狀態(tài)表示每個(gè)階段開始所處的自然狀況和客觀條件，它描述了研究問(wèn) 題過(guò)程中的狀況，又稱不可控因素。決策：決策表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定(或 選擇)，從而確定下一階段的狀態(tài)，這種決定稱

3、為決策，在最優(yōu)控制中也稱為 控制。描述決策的變量，稱為決策變量。策略：由所有階段的決策組成的決策函數(shù)序列稱為全過(guò)程策略，簡(jiǎn)稱策略。狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò) 程。指標(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ī)劃的思路1、采用動(dòng)態(tài)規(guī)劃來(lái)解決問(wèn)題，必須符合兩個(gè)重要的條件。“過(guò)去的歷史只能通過(guò)當(dāng)前狀態(tài)去影響它未來(lái)的發(fā)展，當(dāng)前的狀態(tài)是對(duì)以往 歷史的一個(gè)總結(jié)”，這種特性稱為無(wú)后效性，是多階段決策最優(yōu)化問(wèn)題的特征。作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何， 對(duì)前面的決策所形成的

4、狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)言之，一 個(gè)最優(yōu)策略的子策略總是最優(yōu)的。這就是最優(yōu)化原理。2、如果碰到一個(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ī)劃解題的一些技巧由于動(dòng)態(tài)規(guī)劃并沒有一個(gè)定式，這就需要去開拓我們創(chuàng)造力去構(gòu)造并且使用 它。以下，通過(guò)一些具體的競(jìng)賽實(shí)例談?wù)勈褂脛?dòng)態(tài)規(guī)劃過(guò)程中的一些技巧。數(shù)塔問(wèn)題:有形如圖1.3-8所示

5、的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右 走，一起走到底層，要求找出一條路徑，使路徑上的值最大。19710 416圖 1.3-8這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下（如40），則需要列舉出的路徑 條數(shù)將是一個(gè)非常龐大的數(shù)目。如果用貪心法又往往得不到最優(yōu)解。在用動(dòng)態(tài)規(guī)劃考慮數(shù)塔問(wèn)題時(shí)可以自頂向下的分析，自底向上的計(jì)算。從頂點(diǎn)出 發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到 最大值，只要左右兩道路徑上的最大值求出來(lái)了才能作出決策。同樣的道理下一 層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層 推下去，直到倒數(shù)第二層時(shí)就非常明了。如數(shù)

6、字2,只要選擇它下面較大值的結(jié) 點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最 大值。實(shí)際求解時(shí)應(yīng)掌握其編程的一般規(guī)律，通常需要哪幾個(gè)關(guān)鍵數(shù)組來(lái)存儲(chǔ)變化過(guò)程 這一點(diǎn)非常重要。數(shù)塔問(wèn)題的樣例程序如下：var a:array1.50,1.50,1.3 of longint;第一維記原狀態(tài)，第二維參與計(jì)算，第三維記錄決策，0向左，1向右。浪費(fèi)啊， 不如開三個(gè)一維，或三元組（指針處理麻煩，類似三角矩陣存儲(chǔ)） i,j,n:integer;beginwrite（ please input the number of rows:）;readln（n）;for i:=1 to n do

7、for j: = 1 to i do 行元素?cái)?shù)等于行數(shù)beginread（ai,j,1）;ai,j,2:=ai,j,1;ai,j,3:二0end;計(jì)算=for i:=n-1 downto 1 do 行選擇（始于倒數(shù)第二行），階段for j: = 1 to i do 列選擇，狀態(tài)if ai+1,j,2ai+1,j+1,2 then 左強(qiáng)begin ai,j,2:=ai,j,2+ai+1,j,2;累 計(jì)結(jié)果 （父 + 左）ai,j,3:二0 記錄決策（選左）endelse右強(qiáng)begin ai,j,2:=ai,j,2+ai+1,j+1,2; （累 計(jì)結(jié)果（父 + 右）ai,j,3:二1記錄決策（選右

8、） end;=二輸出=writeln（max=,a1,1,2）;最大值j: = 1;for i:=1 to n-1 dobeginwrite（ai,j,1,-）;j:=j+ai,j,3end;writeln(an,j,1) end.總結(jié)：此題是最為基礎(chǔ)的動(dòng)態(tài)規(guī)劃題目，階段，狀態(tài) 的劃分一目了然。而決策的記錄，充分體現(xiàn)了動(dòng)態(tài)規(guī)劃即“記憶 化搜索”的本質(zhì)。最短路徑問(wèn)題B1-C2B20304現(xiàn)在，我們想從城市a到達(dá)城市E。怎樣走才能使得路徑最短，最短路徑的長(zhǎng)度 是多少？設(shè)DiS x為城市x到城市E的最短路徑長(zhǎng)度（x表示任意一個(gè)城市）；mapi，j表示i，j兩個(gè)城市間的距離，若mapi，j=0，則兩個(gè)

9、城市不通；我們可以使用回溯法來(lái)計(jì)算DiS x：varS：未訪問(wèn)的城市集合；function search(who(x)： integer；的最短距離beginif Who = E Then Search0求城市who與城市E找到目標(biāo)城市Else beginminmaxint ；初始化最短路徑為最大下圖給出了一個(gè)地圖，地圖中每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的連線代表道 路，連線上的數(shù)值代表道路長(zhǎng)度。for i取遍所有城市Doif (mapWho, i 0(有路) and (i S 未訪問(wèn)) then begin置訪問(wèn)標(biāo)志（累加城市E至城市Who的路徑長(zhǎng)度（回溯后，恢復(fù)城市i未訪問(wèn)狀態(tài)（如果最短則

10、記下（返回最短路徑長(zhǎng)度（計(jì)算最短路徑長(zhǎng)度S-Si；jmapWho, i+ search(i)；S-S+i；if jVmin Then min-j；end； (thensearchmin；End； (elseEnd； (searchbeginS除E外的所有城市；Disa search (a)；輸出 Disa；end. (main 這個(gè)程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問(wèn)過(guò)的城市外，其他城 市都要訪問(wèn)，所以時(shí)間復(fù)雜度為O （n!）,這是一個(gè)“指數(shù)級(jí)”的算法。那么， 還有沒有效率更高的解題方法呢？首先，我們來(lái)觀察上述算法。在求bl到E的最短路徑的時(shí)候，先求出從C2到E 的最短路徑；而在求

11、從b2剄E的最短路徑的時(shí)候，又求了一遍從C2剄E的最短 路徑。也就是說(shuō)，從C2到E的最短路徑求了兩遍。同樣可以發(fā)現(xiàn)，在求從Cl、 C2剄E的最短路徑的過(guò)程中，從Dl到E的最短路徑也被求了兩遍。而在整個(gè)程 序中，從Dl到E的最短路徑被求了四遍，這是多么大的一個(gè)浪費(fèi)??！如果在求 解的過(guò)程中，同時(shí)將求得的最短路徑的距離“記錄在案”，以便將來(lái)隨時(shí)調(diào)用， 則可以避免這種重復(fù)計(jì)算。至此，一個(gè)新的思路產(chǎn)生了，即 由后往前依次推出每個(gè)Dis值，直到推出Disa為止。問(wèn)題是，究竟什么是“由后往前”呢？所謂前后關(guān)系是指對(duì)于任意一對(duì)城市i 和j來(lái)說(shuō)，如果滿足“或者城市i和城市j不連通或者disi+mapi，j Nd

12、isj ” 的條件，則定義為城市i在前、城市j在后。因?yàn)槿绻鞘衖和城市j連通且 Disi+mapi，jVDisj，則說(shuō)明城市j至城市E的最短路徑長(zhǎng)度應(yīng)該比 Disj更優(yōu)。可城市j位于城市i后不可能推出此情況，以至于影響最后的解。 那么，我們應(yīng)該如何劃分先后次序呢？3/Z 盼段0階段1階段3粉段4如上圖所示，從城市a出發(fā)，按照與城市a的路徑長(zhǎng)度劃分階段。階段0包含的出發(fā)城市有a階段1所含的城市有bl，b2階段2包含的出發(fā)城市有Cl，C2, C3, C4階段3包含的出發(fā)城市有Dl，D2, D3階段4包含城市E這種劃分可以明確每個(gè)城市的次序，因?yàn)殡A段的劃分具有如下性質(zhì)階段i的取值只與階段i+1有關(guān)

13、，階段i+1的取值只對(duì)階段i的取值產(chǎn)生影響:每個(gè)階段的順序是確定的，不可以調(diào)換任兩個(gè)階段的順序；我們從階段4的城市E出發(fā)，按照階段的順序倒推至階段0的城市a。在求解的各個(gè)階段，利用了燈階段與k+Ld階段之間的如下關(guān)系X, y) g Gdiskx= yGk+1階段的城市集”dis4E=0k=4, 3，0，其中diskx指k階段的城市x。由此得出程序disE-0；for k3 downto 0 do倒序枚舉階段for x取遍k階段的所有城市dobegindisx -8；初始化最短路徑為最大for y 取遍 k+1 階段的所有城市 do if disy+mapx,yhi)為最佳方案，則記下hi hj

14、+1； wi j；end； (then(調(diào)整一套系統(tǒng)if hibest能攔截的最多導(dǎo)數(shù)then begin besthi ； one i； end； (then end；(for輸出當(dāng)前系統(tǒng)攔截的最多導(dǎo)彈系數(shù)best；3、按照求解途徑給出當(dāng)前系統(tǒng)攔截的導(dǎo)彈序列我們?cè)谟?jì)算攔截最多導(dǎo)彈數(shù)的過(guò)程中，利用記憶表w和one來(lái)確定攔截的最 佳方式。每一項(xiàng)wi記錄了攔截導(dǎo)彈i之后應(yīng)攔截哪一枚導(dǎo)彈可取得hi,而 最佳方案中攔截的第一枚導(dǎo)彈為one。由此可知，最佳攔截次序應(yīng)為onef wone f wwonef i(i=wi)。從導(dǎo)彈one出發(fā)，按照w表的指引，依次輸出當(dāng)前 系統(tǒng)攔截的導(dǎo)彈序列：while on

15、e#wonedobegin輸出導(dǎo)彈one被攔截；onewone；end； (while口 ，輸出導(dǎo)彈one被攔截；搬磚問(wèn)題一個(gè)小孩有N塊磚，他可以用這些磚建造不同的樓梯。樓梯由大小嚴(yán)格遞減的臺(tái) 階組成，不允許有相同大小的臺(tái)階。每一個(gè)樓梯由至少兩個(gè)臺(tái)階組成，而每個(gè)臺(tái) 階至少由一塊磚組成，下面的圖片給出了當(dāng)N=11和N=5的一些例子：N計(jì)算并輸出能由N塊磚組成的樓梯的個(gè)數(shù)Q。你的任務(wù)是根據(jù)給出的輸入數(shù)字 N(5 W N W 500)輸出數(shù)字Q樣例輸入212樣例輸出995645335var i,j,m,n,q:longint;f:array1.225,0.225 of longint;beginfi

16、llchar(f,sizeof(f),0);f3,1:=1;f4,1:=1;readln(n);for i: = 1 to n do fi,i:=1;for i:=5 to n dofor j:=1 to (i+1) div 2-1 dofor m:=j+1 to i-j dofi,j:=fi,j+fi-j,m;q:=0;for i: = 1 to (n+1) div 2-1 doq:=q+fn,i;writeln(q);end.金銀島在金銀島上，人們使用的貨幣的值都為完全平方數(shù)，例如1,4,9289.對(duì)于要支付十元的話就有下列四種辦法。1：十個(gè)一元的錢。2： 一個(gè)四元的，六個(gè)一元的。3：二個(gè)

17、四元的，二個(gè)一元的。4： 一個(gè)九元的，一個(gè)一元的。你的任務(wù)在于對(duì)于給定的錢數(shù)(設(shè)其值少于300)，給出有多少種支付的方法.Sample Input210300Sample Output1427program jinyindao;var y,x,number,i,n,money:integer;moneyrange:array1.20 of longint;f:array0.20,0.300 of longint;a:array1.100 of integer;procedure getdata;beginassign(input,data/a/jinyindao.in);reset(input

18、);for y:=1 to 100 dobeginreadln(ay);if ay=0 then break;end;close(input);end;procedure chuli;var m:integer;beginfor m:=1 to 17 domoneyrangem:=m*m;n:=trunc(sqrt(money);end;begingetdata;for y:=1 to 100 dobeginif ay=0 then breakelsebeginmoney:=ay;chuli;for i:=1 to n dofi,0： = 1；for x:=1 to money dof0,x:

19、=0;f0,0：=1；for i:=1 to n dofor number:=1 to money dobeginif number=moneyrangei thenfi,number:=fi-1,number+fi,number-moneyrangeielse fi,number:=fi-1,number;end;writeln(fn,money);end;end;end.網(wǎng)上的一種方法先把i種貨幣按照面值排序，f(i,n)表示前i種貨幣支付n的方法。，決策是用 不要第 i 種貨幣。有方程：f(i,n)=f(i-1,n)+f(i,n-wi)f(0,0): = 1;vara : array0.

20、300of longint;i,j,k : integer;begina0: = 1;for i:=1 to 17 dobegink:=sqr(i);for j:=0 to 300-k doinc(aj+k,aj);end;repeat readln(k);if k=0 thenbreak;writeln(ak);until k=0;end.stepi,j:=stepi-1,j-vi or stepi-1,j;加分二叉樹【問(wèn)題描述】設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為(l,2,3,n),其中數(shù)字 1,2,3,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)(均為正整數(shù))，記第i個(gè)節(jié)點(diǎn) 的分?jǐn)?shù)為di，t

21、ree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree (也包 含tree本身)的加分計(jì)算方法如下：subtree的左子樹的加分X subtree的右子樹的加分+ subtree的根的分?jǐn)?shù)若某個(gè)子樹為空，規(guī)定其加分為1,葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不 考慮它的空子樹。試求一棵符合中序遍歷為(1,2,3,n)且加分最高的二叉樹tree。要求 輸出；tree的最高加分tree的前序遍歷分析很顯然，本題適合用動(dòng)態(tài)規(guī)劃來(lái)解。如果用數(shù)組valuei,j表示從節(jié)點(diǎn) i到節(jié)點(diǎn)j所組成的二叉樹的最大加分，則動(dòng)態(tài)方程可以表示如下：valuei,j=maxvaluei,i+valuei+1,j,value

22、i+1,i+1+valuei,i*valu ei+2,j,valuei+2,i+2+valuei,i+1*valuei+3,j,valuej-1,j-1+valuei,j- 2*valuej,j, valuej,j+valuei,j-1題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計(jì)算過(guò)程中記下從節(jié)點(diǎn) i到節(jié)點(diǎn)j所組成的最大加分二叉樹的根節(jié)點(diǎn)，用數(shù)組rooti,j表示Ural 1018 二*蘋果樹題目有一棵蘋果樹，如果樹枝有分叉，一定是分2叉(就是說(shuō)沒有只有1個(gè)兒子的結(jié) 點(diǎn))這棵樹共有N個(gè)結(jié)點(diǎn)(葉子點(diǎn)或者樹枝分叉點(diǎn))，編號(hào)為1-N，樹根編號(hào)一定是1。 我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號(hào)來(lái)描

23、述一根樹枝的位置。下面是一顆有4 個(gè)樹枝的樹25 /34 /1現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長(zhǎng)有蘋果。給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。輸入格式第 1 行 2 個(gè)數(shù)，N 和 Q(1=Q= N,1N=100)。N表示樹的結(jié)點(diǎn)數(shù)，Q表示要保留的樹枝數(shù)量。接下來(lái)N-1行描述樹枝的信息。每行3個(gè)整數(shù)，前兩個(gè)是它連接的結(jié)點(diǎn)的編號(hào)。第3個(gè)數(shù)是這根樹枝上蘋果的數(shù) 量。每根樹枝上的蘋果不超過(guò)30000個(gè)。輸出格式一個(gè)數(shù)，最多能留住的蘋果的數(shù)量。解析：因?yàn)轭}目一給出就是二叉的，所以很容易就可以寫出方程：a(I,j):二max(a(i.left,k)+a(i.right,j-k),0

24、=kj then j:=k;end;treedp:二j;End;問(wèn)題描述在大學(xué)里每個(gè)學(xué)生，為了達(dá)到一定的學(xué)分，必須從很多課程里選擇一些課程來(lái)學(xué) 習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之 前學(xué)習(xí)。現(xiàn)在有N門功課，每門課有個(gè)學(xué)分，每門課有一門或沒有直接先修課(若 課程a是課程b的先修課即只有學(xué)完了課程a，才能學(xué)習(xí)課程b)。一個(gè)學(xué)生要從 這些課程里選擇M門課程學(xué)習(xí)，問(wèn)他能獲得的最大學(xué)分是多少？輸入：第一行有兩個(gè)整數(shù)N,M用空格隔開。(1=N=200,1=M=150)接下來(lái)的N行，第I+1行包含兩個(gè)整數(shù)ki和si, ki表示第I門課的直接先修課， si表示第I門課的學(xué)分。

25、若ki=0表示沒有直接先修課(1=ki=N, 1=si=0 then exit;treedp(ax.r,y);只有右子樹的情況j:=bax.r,y;for k:=1 to y do(左右子樹都有的情況begintreedp(ax.l,k-1);treedp(ax.r,y-k);i:=bax.l,k-1+bax.r,y-k+ax.k;if ij then j:=i;end;bx,y:=j;end;beginreadln(s);assign(input,s);reset(input);readln(n,m);fillchar(f,sizeof(f),0);for i:=0 to n dobegin

26、 ai.l:=-1;ai.r:=-1;ai.k:=-1;end;(build treefor i:=1 to n dobeginreadln(k,l);ai.k:=l;if fk=0 then ak.l:=ielse afk.r:=i;fk:=i;end;(bianjiefor i:=-1 to n dofor j:=-1 to m doif (i=-1) or (j=0) then bi,j:=0 else bi,j:=-1;(tree dptreedp(a0.l,m);(outputwriteln(ba0.l,m);end.Tju1053技能樹Problem 玩過(guò)Diablo的人對(duì)技能樹一

27、定是很熟悉的。一顆技能樹的每個(gè)結(jié)點(diǎn)都是一項(xiàng)技 能，要學(xué)會(huì)這項(xiàng)技能則需要耗費(fèi)一定的技能點(diǎn)數(shù)。只有學(xué)會(huì)了某一項(xiàng)技能以后，才能繼續(xù)學(xué)習(xí)它的后繼技能。每項(xiàng)技能又有著不同 的級(jí)別，級(jí)別越高效果越好，而技能的升級(jí)也是需要耗費(fèi)技能點(diǎn)數(shù)的。有個(gè)玩家積攢了一定的技能點(diǎn)數(shù)，他想盡可能地利用這些技能點(diǎn)數(shù)來(lái)達(dá)到最好的 效果。因此他給所有的級(jí)別都打上了分，他認(rèn)為效果越好的分?jǐn)?shù)也越高。現(xiàn)在他要你幫忙尋找一個(gè)分配技能點(diǎn)數(shù)的方案，使得分 數(shù)總和最高。Input該題有多組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)第一行是一個(gè)整數(shù)n（1=n=20），表示所有不同技能的總數(shù)。接下來(lái)依次給出n個(gè)不同技能的詳細(xì)情況。每個(gè)技能描述包括5行。第一行是該技能的

28、名稱。第2行是該技能在技能樹中父技能的名稱，名稱為None則表示該技能不需要任 何的先修技能便能學(xué)習(xí)。第3行是一個(gè)整數(shù)L（1=L=20），表示這項(xiàng)技能所能擁有的最高級(jí)別。第4行共有L個(gè)整數(shù)，其中第I個(gè)整數(shù)表示從地I-1級(jí)升到第I級(jí)所需要的技能 點(diǎn)數(shù)（0級(jí)表示沒有學(xué)習(xí)過(guò)）。第5行包括L個(gè)整數(shù)，其中第I個(gè)整數(shù)表示從第I-1級(jí)升級(jí)到第I級(jí)的效果評(píng)分， 分?jǐn)?shù)不超過(guò)20。在技能描述之后，共有兩行，第1行是一個(gè)整數(shù)P，表示目前所擁有的技能點(diǎn)數(shù)。 接下來(lái)1行是N個(gè)整數(shù)，依次表示角色當(dāng)前習(xí)得的技能級(jí)別，0表示還未學(xué)習(xí)。 這里不會(huì)出現(xiàn)非法情況。Output每組測(cè)試數(shù)據(jù)只需輸出最佳分配方案所得的分?jǐn)?shù)總和。解析：這

29、題是選課的加強(qiáng)版，但并難不倒我們還是把一棵樹轉(zhuǎn)換為二叉樹，完后從子節(jié)點(diǎn)到根節(jié)點(diǎn)作一次dp，最后得到最優(yōu) 解由于和上題很相像就不寫方程了。源代碼程序：program bluewater;type tree=records,sf:string;l,r,m:longint;c:array1.20 of longint;d:array1.20 of longint;end;vari,j,k,l,m,n:longint;a:array0.20 of tree;b:array0.20 of longint;learn:array0.20 of longint;f:array0.20,0.8000 of l

30、ongint;function treedp(x,y:longint):longint;var i,j,k,l,max,o,p,q:longint;beginif fx,y-1 then begin treedp:=fx,y;exit;end;max:二treedp(ax.r,y);learn0if learnx0 thenbeginfor k:=0 to y dobegini:二treedp(ax.l,k)+treedp(ax.r,y-k);if imax then max:=i;end;end;(learn=0l:=0;p:=0;i:=0;for o:=1 to ax.m dobegini

31、f olearnx thenbegin l:=l+ax.co;p:=p+ax.do;end;for k:=0 to y-l dobegini:二treedp(ax.l,k)+treedp(ax.r,y-l-k)+p;if imax then max:=i;end;end;fx,y:二max;treedp:二max;end;function find(x:string):longint;var i,j:longint;beginfor i:=0 to n doif ai.s=x then break;find:=i;end;beginwhile not(eof(input) dobegin(in

32、putreadln(n);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);a0.s:=None;for i:=1 to n dowith ai dobeginreadln(s);readln(sf);readln(m);for j:=1 to m do read(cj);readln;for j:=1 to m do read(dj);readln;end;readln(m);if m8000 then m:=8000;for i:=1 to n do read(learni);readln;(build binary treefor i:=1

33、to n dobegink:=find(ai.sf);if bk=0 thenbegin bk:=i;ak.l:=i;endelse begin abk.r:=i;bk:=i;end;end;(bian jiefor i:=0 to 20 dofor j:=0 to 8000 dofi,j:=-1;for i:=0 to 8000 do f0,i:=0;(mainwriteln(treedp(a0.l,m);end;end.戰(zhàn)略游戲ProblemBob喜歡玩電腦游戲，特別是戰(zhàn)略游戲。但是他經(jīng)常無(wú)法找到快速玩過(guò)游戲的辦 法?，F(xiàn)在他有個(gè)問(wèn)題。他要建立一個(gè)古城堡，城堡中的路形成一棵樹。他要在這棵樹的

34、結(jié)點(diǎn)上放置最少 數(shù)目的士兵，使得這些士兵能了望到所有的路。注意，某個(gè)士兵在一個(gè)結(jié)點(diǎn)上時(shí)，與該結(jié)點(diǎn)相連的所有邊將都可以被了望到。請(qǐng)你編一程序，給定一樹，幫Bob計(jì)算出他需要放置最少的士兵.Input第一行為一整數(shù)M，表示有M組測(cè)試數(shù)據(jù)每組測(cè)試數(shù)據(jù)表示一棵樹，描述如下：第一行N，表示樹中結(jié)點(diǎn)的數(shù)目。第二行至第N+1行，每行描述每個(gè)結(jié)點(diǎn)信息，依次為：該結(jié)點(diǎn)標(biāo)號(hào)i，k（后面有 k條邊與結(jié)點(diǎn)I相連）。接下來(lái)k個(gè)數(shù)，分別是每條邊的另一個(gè)結(jié)點(diǎn)標(biāo)號(hào)r1，r2, .，rk。對(duì)于一個(gè)n（0n=1500）個(gè)結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號(hào)在0到n-1之間，在輸入數(shù)據(jù)中 每條邊只出現(xiàn)一次。Output輸出文件僅包含一個(gè)數(shù)，為所求的

35、最少的士兵數(shù)目。例如，對(duì)于如下圖所示的樹：答案為1（只要一個(gè)士兵在結(jié)點(diǎn)1上）。Sample Input240 1 1 TOC o 1-5 h z 2 2 30053 1 4 21 000 00Sample Output12Sourcesgoi 分析：這題有2種做法，一種是比較簡(jiǎn)單但不是很嚴(yán)密的貪心，如果測(cè)試數(shù)據(jù)比 較刁鉆的話就不可能ac，而這題是一道比較典型的樹型動(dòng)態(tài)規(guī)劃的題目，這題 不但要考慮子節(jié)點(diǎn)對(duì)他的根節(jié)點(diǎn)的影響，而且每放一個(gè)士兵，士兵所在位置既影 響他的子節(jié)點(diǎn)也影響了他的根節(jié)點(diǎn)。不過(guò)狀態(tài)還是很容易來(lái)表示的，動(dòng)規(guī)實(shí)現(xiàn)也 不是很難，不過(guò)這在這些例題中也有了些“創(chuàng)新”了。而且這題不是一個(gè)對(duì)二

36、叉 樹的dp，而是對(duì)一顆普通樹的dp，所以更具代表性。源程序代碼：program bluewater;constmaxn=1500;vari,j,k,l:longint;m,n,p,q:longint;a:array0.maxn,0.maxn of boolean;b:array0.maxn of longint;c:array0.maxn of boolean;function leaf(x:longint):boolean;var i,j:longint;t:boolean;begint:=true;for i:=0 to n-1 doif ax,i then begin t:=false

37、;break;end;leaf:=t;end;function treedp(x:longint):longint;var i,j,k,l:longint;beginj:=0;addk:=0;leafl:=0;(not put not leaffor i:=0 to n-1 doif (ax,i) and (xi) thenif leaf(i) then inc(k) elsebeginj:=j+treedp(i);if not(ci) then inc(l);end;puanduanif (k0) or (l0) then begin cx:=true;treedp:=j+1;exit;en

38、d;if (j0) and (l=0) then begin treedp:二j;exit;end;end;begininputreadln(m);for p:=1 to m dobeginfillchar(b,sizeof(b),0);fillchar(a,sizeof(a),false);fillchar(c,sizeof(c),false);readln(n);for i:=1 to n dobeginread(k,l);for j:=1 to l dobeginread(q);ak,q:二true;bq:=1;end;readln;end;mainfor i:=0 to n-1 doi

39、f bi=0 then break;fillchar(b,sizeof(b),0);if leaf(i) then writeln(l) else writeln(treedp(i);end;end.(最長(zhǎng)上升子序列)描述：給一隊(duì)排列整齊的數(shù)列ai,找到數(shù)列ai中最長(zhǎng)上升子序列。輸入：第一行是數(shù)列的元素個(gè)數(shù)匕第二行是N個(gè)整數(shù)，范圍從0到10,000。 (1=N=1000)輸出：包括一個(gè)整數(shù)，表示最長(zhǎng)上升子序列的長(zhǎng)度。Sample Input71 7 3 5 9 4 8Sample Output4題解：經(jīng)典的Dp問(wèn)題，求最長(zhǎng)上升子序列。我用的是O(N”2)的方法。狀態(tài)轉(zhuǎn)移方程是di=maxdk

40、+ 1)(ki且akaj)and(dimax then max:=di;writeln(max);end;begininit;dp;findmax;end.方法二pascal動(dòng)態(tài)規(guī)劃里的最長(zhǎng)上升子序列vara,fDP 記錄,p后面的:array1.1000of longint; i,j,k,n:longint;beginreadln(n);for i:=1 to n dobeginread(ai);fi:=1;(預(yù)處理end;for i:=n-1 downto 1 dofor j:=n downto i+1 doif (aiaj)and(fijthen beginj:=fi;k:=i;end;

41、writeln(j);while k0 dobeginwrite(k,);k:=pk;end;end.這是n2的算法，大牛會(huì)寫nlog(n)的算法，就是用堆來(lái)優(yōu)化方法三Program upzxl;Var n,I,j,maxi,maxlen:longint;A,f:array1.1000 of longint;F1,f2:text;BeginAssign(f1, input.txt)；reset(f1);Assign(f2, output.txt)；rewrite(f2);Readln(f1,n);For i:=1 to n do read(f2,ai);F1: = 1;For i:=2 to

42、n dobeginmaxi:=0;for j:=1 to i-1 do if aiaj then if maxifj then maxi:=fj;fi:二maxi+1;end;maxlen:=0;for i:=1 to n do if maxlenfi then maxlen:=fi;writeln(f2,maxlen);close(f1);close(f2);end.巡回演出題目描述：Flute市的Phlharmoniker樂團(tuán)2000年準(zhǔn)備到Harp市做一次大型演出，本著普及古典音樂 的目的，樂團(tuán)指揮準(zhǔn)備在到達(dá)Harp市之前先在周圍一些小城市作一段時(shí)間的巡回演出，此 后的幾天里，音樂家們將

43、每天搭乘一個(gè)航班從一個(gè)城市飛到另一個(gè)城市,最后才到達(dá)目的地Harp 市(樂團(tuán)可多次在同一城市演出).由于航線的費(fèi)用和班次每天都在變,城市和城市之間都有一份循環(huán)的航班表,每一時(shí)間，每一 方向，航班表循環(huán)的周期都可能不同.現(xiàn)要求尋找一張花費(fèi)費(fèi)用最小的演出表.輸入：輸入文件包括若干個(gè)場(chǎng)景.每個(gè)場(chǎng)景的描述由一對(duì)整數(shù)n(2=n=10)和k(1=k=1000)開始, 音樂家們要在這n個(gè)城市作巡回演出，城市用1.n標(biāo)號(hào)，其中1是起點(diǎn)Flute市,n是終點(diǎn)Harp 市，接下來(lái)有n*(n-1)份航班表，一份航班表一行，描述每對(duì)城市之間的航線和價(jià)格,第一組n-1份 航班表對(duì)應(yīng)從城市1到其他城市(2,3,.n)的航

44、班，接下的n-1行是從城市2到其他城市 (1,3,4.n)的航班，如此下去.每份航班又一個(gè)整數(shù)d(1=d=30)開始，表示航班表循環(huán)的周期，接下來(lái)的d個(gè)非負(fù)整數(shù)表示 1,2.d天對(duì)應(yīng)的兩個(gè)城市的航班的價(jià)格，價(jià)格為零表示那天兩個(gè)城市之間沒有航班.例如3 75 0 80表示第一天機(jī)票價(jià)格是75KOI,第二天沒有航班，第三天的機(jī)票是80KOI,然后循環(huán):第四天又 是75KOI,第五天沒有航班，如此循環(huán).輸入文件由n=k=0的場(chǎng)景結(jié)束.輸出：對(duì)每個(gè)場(chǎng)景如果樂團(tuán)可能從城市1出發(fā)，每天都要飛往另一個(gè)城市,最后(經(jīng)過(guò)k天)抵達(dá)城市n,則輸出這k個(gè)航班價(jià)格之和的最小值.如果不可能存在這樣的巡回演出路線，輸出0

45、.樣例輸入：3 6130 15075 0 807 120 110 0 100 110 120 060 70 60 503 0 135 1402 70 802 32 0 701 800 0樣例輸出：4600初看這道題，很容易便可以想到動(dòng)態(tài)規(guī)劃，因?yàn)榈趚天在第y個(gè)地方的最優(yōu)值只與第x-1天有 關(guān)，符合動(dòng)態(tài)規(guī)劃的無(wú)后效性原則，即只與上一個(gè)狀態(tài)相關(guān)聯(lián)，而某一天x航班價(jià)格不難求出 S=C(x-1) mod m +1.我們用天數(shù)和地點(diǎn)來(lái)規(guī)劃用一個(gè)數(shù)組A1.1000,1.10來(lái)存儲(chǔ),Ai,j表 示第i天到達(dá)第j個(gè)城市的最優(yōu)值,Ci,j,l表示i城市與j城市間第l天航班價(jià)格，則 Ai,j=MinAi-1,l+

46、Cl,j,i (l=1.n 且 Cl,j,i0),動(dòng)態(tài)規(guī)劃方程一出，盡可以放懷大笑 了.示范程序:program p erf or m_hh;varf_, f out ： teKt;p, L i, .Sn,k： integer;a： array 1. . 1000 1. . 10 of integer; 動(dòng)態(tài)規(guī)劃數(shù)組c： array 1. . 10,1. . 10 of record 航EE價(jià)格數(shù)組num：integer;t:array 1.30 of integer;end;e：array 1. . 1000 of integer;procedure work;begin人工賦第一天各城市最

47、優(yōu)值for i：=l to n dobeginif c lj i. t 1 0then alj i ： = c 13 i. t 1;end;for i：=2 to k dobeginIfor j：=1 to n dobeginfor 1：=1 to n dobeginif (jOl)and (c 1, j. t (il) mod c 1, j. nnni+1 0) 判斷存在航班and (ai_, j=0)or (ai-lj l+c 1., j. t (i_l) mod c 1., j. num+1 ai_, j) 判斷比當(dāng)前解憂then ai., j ：=31-1, l+c 1, j. t (

48、i-l) mod c 1., j. num+1; 賦值end;end;end;ep ：=ak, n ; 第口個(gè)場(chǎng)景的最優(yōu)值end;procedure readfile;讀文件beginassign(f_,J PERFORM. DAT5 ) ; reset (f);assign(tout,3 PERFORM.OUT ); rewrite (tout)readln(f _,k) ; p：=0;while (n0) anddobeginP:=P+1；fillchar (c_, sizeof (c) 0);fillchar(a, sizeof(a)0);for i：=l to n dobeginfor

49、 j：=1 to i-l dobeginread(f_, c i., j. num);for 1： = 1 to c i., j . num doread(f, c i, j. t 1);end;for j：=i+l to n dobeginread(f_, c i., j. num);for 1： = 1 to c i., j . num doread(f, c i., j. t 1);end;end;work;xeadln (f., k);end;輸出各個(gè)場(chǎng)景的解for i：=l to p-l dowiitelnff out, e i) write(fout, ep);I close (f

50、);close(fout);end;beginreadfile;end.動(dòng)態(tài)規(guī)劃作業(yè)最長(zhǎng)公共子序列問(wèn)題LCS問(wèn)題描述一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說(shuō)，若 給定序列X=x1, x2,，xm，則另一序列Z=z1, z2,，zk是X的子序列是 指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列i1, i2,., ik，使得對(duì)于所有j=1,2,.,k 有例如，序列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,

51、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)公共子序列，因?yàn)閄 和Y沒有長(zhǎng)度大于4的公共子序列。最長(zhǎng)公共子序列(LCS)問(wèn)題：給定兩個(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è)。樣例輸入：LCS.