(整理)深入分析區(qū)間型動(dòng)態(tài)規(guī)劃

1、 3/3(整理)深入分析區(qū)間型動(dòng)態(tài)規(guī)劃. 深入分析區(qū)間型動(dòng)態(tài)規(guī)劃 鄭州市第九中學(xué)張旭祥 區(qū)間型動(dòng)態(tài)規(guī)劃在信息學(xué)競(jìng)賽中應(yīng)用甚廣，它是動(dòng)態(tài)規(guī)劃中的經(jīng)典問(wèn)題，最小代價(jià)字母樹(shù)是這類動(dòng)態(tài)規(guī)劃最經(jīng)典的體現(xiàn)，對(duì)于初學(xué)者而言這類動(dòng)態(tài)規(guī)劃并不太好理解。于是，區(qū)間型動(dòng)態(tài)規(guī)劃又成了動(dòng)態(tài)規(guī)劃中的難點(diǎn)問(wèn)題。下面，本文將為大家深入分析區(qū)間型動(dòng)態(tài)規(guī)劃的思想及其程序的實(shí)現(xiàn)，希望能對(duì)大家有所幫助。 歷屆大賽中區(qū)間型動(dòng)態(tài)規(guī)劃題目的考查。 區(qū)間型動(dòng)態(tài)規(guī)劃是各大信息競(jìng)賽出題的熱點(diǎn)，具體體現(xiàn)在以下題目： 1.合并石子NOI1995 2.能量項(xiàng)鏈NOIP2006 3.加分二叉樹(shù)NOIP2003 4.最優(yōu)排序二叉樹(shù) CTSC96 這些題目

2、出現(xiàn)的頻次及其所在比賽的重要性足以說(shuō)明區(qū)間型動(dòng)態(tài)規(guī)劃在各類動(dòng)態(tài)規(guī)劃中有著舉足輕重的地位。 二、區(qū)間型動(dòng)態(tài)規(guī)劃的算法分析 在這里就以經(jīng)典的最小代價(jià)字母樹(shù)作為例子，對(duì)區(qū)間型動(dòng)態(tài)規(guī)劃的算法進(jìn)行分析。 問(wèn)題描述： 給定一個(gè)序列，如4、1、2、3我們將他們相加進(jìn)行合并，最終合并成一個(gè)數(shù)，每次相加的代價(jià)是兩個(gè)加數(shù)的和，求怎樣的相加順序可以使總代價(jià)最小。 很多初學(xué)者認(rèn)為這類動(dòng)態(tài)規(guī)劃不易理解，其重要原因是這類動(dòng)態(tài)規(guī)劃與其他動(dòng)態(tài)規(guī)劃的思想不大相同，而初學(xué)者又是利用其他動(dòng)態(tài)規(guī)劃的思想來(lái)解決這類動(dòng)態(tài)規(guī)劃，從而進(jìn)入了思維誤區(qū)。這種錯(cuò)誤的思維模式一旦建立便很難重新建立正確的解題思想，從而陷入絕境。 這類動(dòng)態(tài)規(guī)劃正確的解

3、法是這樣的： 首先，根據(jù)動(dòng)態(tài)規(guī)劃無(wú)后效性的性質(zhì)可以想到：對(duì)于一個(gè)序列：A1、A2An，假如最后相加的兩個(gè)數(shù)是第一個(gè)數(shù)到第i個(gè)數(shù)的和S1-i以及第i+1個(gè)數(shù)到第n個(gè)數(shù)的和Si+1-n，另外，對(duì)于第一個(gè)數(shù)到第i個(gè)數(shù)相加的最小代價(jià)是F1,i以及從第i+1到第n個(gè)數(shù)相加的最小代價(jià)為Fi+1,n，則總代價(jià)即為Fi+1,n+F1,i(前面相加的最小代價(jià))+ S1-i+ Si+1-n（最后一次相加的最小代價(jià)）。由此，我們可以清楚的看出要想求出總代價(jià)的最小值只要枚舉i的位置，使得Fi+1,n+F1,i + S1-i+ Si+1-n的和最小即可。綜上所述我們可以總結(jié)出狀態(tài)轉(zhuǎn)移方程： FI,J:=minFI,k+

4、Fk+1,j+SI,k+Sk+1,j 狀態(tài)轉(zhuǎn)移數(shù)組F即代表從第i個(gè)數(shù)到第j個(gè)數(shù)相加的最小代價(jià)，S數(shù)組為預(yù)處理好的從第i 個(gè)數(shù)到第j個(gè)數(shù)的和。 核心代碼如下： For i:=1 to n do For j:=1 to n-I do For k:=j to i+j-1 do If Fj,i+jFj,k+Fk+1,i+j+Sj,k+Sk+1,i+j then Fj,i+j:=Fj,k+Fk+1,i+j+Sj,k+Sk+1,i+j; 最小值A(chǔ)NS為F1,n. 二、區(qū)間型動(dòng)態(tài)規(guī)劃的具體應(yīng)用 1、石子歸并 題目描述： 在一個(gè)圓形操場(chǎng)的四周擺放著N堆石子(NFj,k+Fk+1,i+j+Sj,k+Sk+1,i

5、+j then Fj,i+j:=Fj,k+Fk+1,i+j+Sj,k+Sk+1,i+j; For i:=1 to n-1 do Ans:=minFi,i+n-1 最小值為Ans 從代碼中可以看出這道題的寫法跟最小代價(jià)字母樹(shù)的區(qū)別在于枚舉起點(diǎn)的時(shí)候長(zhǎng)度增加到了2*n，并且在最后求解的時(shí)候也需要枚舉起點(diǎn)，求長(zhǎng)度為n的最小值，這恰恰是利用了區(qū)間型動(dòng)態(tài)規(guī)劃的特點(diǎn)。當(dāng)然，在讀入數(shù)據(jù)的時(shí)候需要把初始數(shù)組的長(zhǎng)度擴(kuò)大一倍然后再進(jìn)行預(yù)處理即可。這種方法在能量項(xiàng)鏈一題中還有具體的體現(xiàn)，因?yàn)槟芰宽?xiàng)鏈的核心算法與本題幾乎一樣，所以就不再贅述。大家可以自己練習(xí)。 2、加分二叉樹(shù) 【問(wèn)題描述】 設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹(shù)tr

6、ee的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第j個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹(shù)都有一個(gè)加分，任一棵子樹(shù)subtree（也包含tree本身）的加分計(jì)算方法如下： subtree的左子樹(shù)的加分 subtree的右子樹(shù)的加分subtree的根的分?jǐn)?shù) 若某個(gè)子樹(shù)為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹(shù)。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹(shù)tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷 【輸入格式】 第1行：一個(gè)整數(shù)n（n30），為節(jié)點(diǎn)個(gè)數(shù)。 第2行

7、：n個(gè)用空格隔開(kāi)的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)100）。 【輸出格式】 第1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過(guò)4,000,000,000）。 第2行：n個(gè)用空格隔開(kāi)的整數(shù)，為該樹(shù)的前序遍歷。 【輸入樣例】 5 5 7 1 2 10 【輸出樣例】 145 3 1 2 4 5 這道題目巧妙地將區(qū)間型動(dòng)態(tài)規(guī)劃和二叉樹(shù)相結(jié)合，既考查了二叉樹(shù)的基本性質(zhì)又考查了大家對(duì)動(dòng)態(tài)規(guī)劃的掌握，不得不承認(rèn)這是一道經(jīng)典好題。同樣，這道題最后要求輸出前序遍歷，只需要用遞歸建樹(shù)即可，這里就不多說(shuō)了。具體的預(yù)處理過(guò)程和動(dòng)態(tài)規(guī)劃過(guò)程如下： 預(yù)處理 read(n); For i:=1 to n do read(ai); For i:=0 to n do For j:=0 to n do Fi,j:=1; For i:=1 to n do Fi,i:=ai; DP For i:=2 to n do For j:=1 to n-i+1 do For k:=j to i+j-1 do if fj,i+j-1fj,k-1*fk+1,i+j-1+ak then fj,i+j-1:=fj,k-1*fk+1,i+j-1+ak; 其中Ak是讀入的數(shù)組，F(xiàn)1,n同樣為最終結(jié)果，表示從第一個(gè)到第n個(gè)數(shù)進(jìn)行建樹(shù)的最大價(jià)值。 小結(jié)：對(duì)于區(qū)