動態(tài)規(guī)劃程序設計5

1、安陽一中信息學奧賽輔導資料動態(tài)規(guī)劃程序設計 5區(qū)間型動態(tài)規(guī)劃在信息學競賽中應用甚廣，它是動態(tài)規(guī)劃中的經(jīng)典問題，最小代價字母樹是這 類動態(tài)規(guī)劃最經(jīng)典的體現(xiàn)，對于初學者而言這類動態(tài)規(guī)劃并不太好理解。于是，區(qū)間型動態(tài)規(guī)劃又 成了動態(tài)規(guī)劃中的難點問題。* 歷屆大賽中區(qū)間型動態(tài)規(guī)劃題目的考查。區(qū)間型動態(tài)規(guī)劃是各大信息學競賽出題的熱點，具體體現(xiàn)在以下題目：1 合并石子 NOI l9952 能量項鏈 NOIP 20063 加分二叉樹 NOIP 20034 最優(yōu)排序二又樹 ctsc 96 這些題目出現(xiàn)的頻次及其所在比賽的重要性足以說明區(qū)間型動態(tài)規(guī)劃在各類動態(tài)規(guī)劃中有著舉 足輕重的地位。區(qū)間類模型的動態(tài)規(guī)劃 ,

2、一般是要求整段區(qū)間的最優(yōu)值 ,子問題一般是把區(qū)間分成兩個子區(qū)間。一 般用二維數(shù)組表示狀態(tài) ,例如 fi,j 表示從 i 到 j 的最優(yōu)值 ,則狀態(tài)轉移方程就是跟子區(qū)間之間的關系。一、區(qū)間型動態(tài)規(guī)劃的算法分析在這里就以經(jīng)典的最小代價字母樹作為例子，對區(qū)間型動態(tài)規(guī)劃的算法進行分析。問題描述：給定一個序列，如 4， 1，2， 3，我們將它們相加進行合并，最終合并成一個數(shù)，每次相加的代 價是兩個加數(shù)的和，求怎樣的相加順序可以使總代價最小。很多初學者認為這類動態(tài)規(guī)劃不易理解，其重要原因是這類動態(tài)規(guī)劃與其他動態(tài)規(guī)劃的思想不 大相同，而初學者又是利用其他動態(tài)規(guī)劃的思想來解決這類動態(tài)規(guī)劃，從而進入了思維誤區(qū)。

3、這種 錯誤的思維模式一旦建立便很難重新建立正確的解題思想，從而陷入絕境。這類動態(tài)規(guī)劃正確的解法是這樣的：首先，根據(jù)動態(tài)規(guī)劃無后效性的性質可以想到：對于一個序列：A1，A2, An，假 如最后相加的兩個數(shù)是第一個數(shù)到第 i 個數(shù)的和 s1 i 以及第 i+1 個數(shù)到第 n 個數(shù)的和 si+1 n ，另外， 對 于第一個數(shù)到第 i 個數(shù)相加的最小代價是 Fl ，i 以及從第 i+1 到第 n 個數(shù)相加的最小代價為 Fi+1 ， n ，則總代價即為 Fi+1 ，n+F1 ，i（ 前面相加的最小代價 ）+s1 i+si+1 n（ 最后一次相加的 最小代價 ） 。由此，我們可以清楚地看出要想求出總代價的

4、最小值只要枚舉 i 的位置，使得 Fi+1 ， n+F1 ，i+S1-i+si+1n 的和最小即可。綜上所述，我們可以總結出狀態(tài)轉移方程：Fi ，J ： =rainFi ，k+Fk+1 ， j+Si ，k+Sk+1 ，j）狀態(tài)轉移數(shù)組 F 即代表從第 i 個數(shù)到第 j 個數(shù)相加的最小代價， s 數(shù)組為預處理好的從第 i 個數(shù) 到第 j 個數(shù)的和。核心代碼如下：For i ： =1 to n doFor j ： =1 to n-I doFor k： =j to i+j-1 doIf fj,i+jfj,k+fk+1,I+j+sj,k+sk+1,I+jThen fj,I+j= fj,k+fk+1,I

5、+j+sj,k+sk+1,I+j安陽一中信息學奧賽輔導資料最小值 ANS為 F1 ， n 。二、區(qū)間型動態(tài)規(guī)劃的具體應用例 1 ：問題描述給定一個具有 N(N50)個頂點(從1到N編號)的凸多邊形 ,每個頂點的權均已知。問如何把這個 凸多邊形劃分成 N-2 個互不相交的三角形 ,使得這些三角形頂點的權的乘積之和最小?輸入文件 :第一行頂點數(shù) N第二行 N 個頂點 (從 1到 N)的權值輸出格式 :最小的和的值各三角形組成的方式輸入示例 :5121 122 123 245 231輸出示例 :The minimum is:12214884The format ion of 3 triangle:3

6、 4 5, 1 5 3, 1 2 3題目解析這是一道很典型的區(qū)間類型動態(tài)規(guī)劃問題。設 FI,J(IJ) 表示從頂點 I 到頂點 J 的凸多邊形三角 剖分后所得到的最大乘積 ,我們可以得到下面的動態(tài)轉移方程 :FI,J=MinFI,K+FK,J+SI*SJ*SK) (IKb then min:=b else min:=a;end;procedure digui(x,y:longint);beginif dgx,y=0 then exit;digui(x,dgx,y);第 2 頁 共 6 頁安陽一中信息學奧賽輔導資料digui(dgx,y,y);if bj thenbeginwrite(x, ,d

7、gx,y, ,y);bj:=false;endelsewrite(, ,x, ,dgx,y, ,y);end;beginreadln(n);for i:=1 to n dobeginread(Si);end; readln; fillchar(f,sizeof(f),$7f); fillchar(dg,sizeof(dg),0); for i:=1 to n do fi,i+1:=0;/ 數(shù)據(jù)賦初值for jj:=2 to n-1 do/枚舉多邊形邊數(shù)for i:=1 to n-1 do / 枚舉起點beginif i+jjn then break;j:=i+jj;for k:=i+1 to

8、j-1 dobegintt:=fi,k+fk,j+si*sj*sk;/DP 轉移方程 if fi,jtt thenbegin fi,j:=tt; dgi,j:=k; / 記錄中間點，以便輸出劃分方法 end;end;end;writeln(f1,n); bj:=true; digui(1,n); writeln;end.例 2 石子歸并題目描述：安陽一中信息學奧賽輔導資料在一個圓形操場的四周擺放著 N堆石子 (N l00) ，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次 只能選取相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。編一程序， 由文件讀入堆棧數(shù) N及每堆棧的石子數(shù) (2

9、0) 。(1) 選擇一種合并石子的方案，使用權得做N-1 次合并，得分的總和最?。?2) 選擇一種合并石子的方案，使用權得做N-1 次合并，得分的總和最大。輸入數(shù)據(jù)：第一行為石子堆數(shù) N：第二行為每堆的石子數(shù)，每兩個數(shù)之間用一個空格分隔。輸出數(shù)據(jù)：從第一至第 N行為得分最小的合并方案。 第 N+I 行是空行。 從第 N+2行到第 2N+1 行是得分最大 的合并方案。每種合并方案用 N行表示，其中第 i 行(1i N)表示第 i 次合并前各堆的石子數(shù) (依 順時針次序輸出，哪一堆先輸出均可) 。要求將待合并的兩堆石子數(shù)以相應的負數(shù)表示。輸入輸出范例：輸入：44 5 9 4輸出：-4 5 9 -4

10、-8 -5 9-1 3 -9224 -5 -9 44 14 -4-4 -1 822這道題目可以說跟最小代價字母樹只有兩個不同的地方，一個是所求序列是一個環(huán)形的，另一 個是要求輸出方案。對于輸出方案而言，只需要用一般動態(tài)規(guī)劃記錄方案的方法即可，因為不是本 文的重點在此就不再深究。對于所求序列是環(huán)形的問題其實只需要用一個小小的技巧便輕松解決， 請先看代碼：/ 預處理Read(n) ：For I:=1 to n doBeginRead(aI)a i+n : =a i ;End;For i:=l to n doFor j:=l to n doFor k:=i to j doSI, j: =SI, j+

11、a k;/DP 過程For i:=1 to n doFor j:=l to 2*n-I doFor k:=j to i+j-1 do安陽一中信息學奧賽輔導資料If Fj, i+jFj, k+Fk+l, i+j+S j, k+Sk+l, i+jthen Fj, i+j: =Fj, k+Fk+l, i+j+Sj, k+Sk+l, i+j;For i:=1 to n-1 doAns: =minFi, i+n-1最小值為 Ans 從代碼中可以看出，這道題的寫法跟最小代價字母樹的區(qū)別在于權舉起點的時候長度增加到了2*n ，并且在最后求解的時候也需要枚舉起點，求長度為n 的最小值，這恰恰是利用了區(qū)間型動態(tài)

12、規(guī)劃的特點。當然，在讀入數(shù)據(jù)的時候需要把初始數(shù)組的長度擴大一倍然后再進行預處理即可。這種 方法在能量項鏈一題中還有具體的體現(xiàn)，因為能量項鏈的核心算法與本題幾乎一樣，所以就不再贅 述。大家可以自己練習。例 3 加分二叉樹【問題描述】設一個 n個結點的二叉樹 tree 的中序遍歷為 （1，2，3，13），其中數(shù)字 l ，2，3，n為界 點編號。每個結點都有一個分數(shù) （ 均為正整數(shù) ） ，記第 j 個結點的分數(shù)為 di ，tree 及它的每個子樹都 有一個加分，任一棵子樹 subrtee（ 也包含 tree 本身 ） 的加分計算方法如下：subtree 的左子樹的加分 subtree 的右子樹的加分

13、 +subtree 的根的分數(shù) 若某個子樹為空，規(guī)定其加分為 l ，葉子的加分就是葉結點本身的分數(shù)。不考慮它的空子樹。 試求一棵符合中序遍歷為 （1 ，2，3，n） 且加分最高的二叉樹 tree 。要求輸出：（1）tree 的最高加分（2）tree 的前序遍歷【輸入格式】第 1 行：一個整數(shù) n（n30） ，為節(jié)點個數(shù)。第 2 行： n 個用空格隔開的整數(shù)，為每個節(jié)點的分數(shù)（ 分數(shù) 100） ?！据敵龈袷健康?1 行：一個整數(shù)，為最高加分 （結果不會超過 4，000，000，000） 。第 2 行： rl 個用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?5 7 1 2 1 0 【輸出樣例】

14、1453 1 2 4 5 這道題目巧妙地將區(qū)間型動態(tài)規(guī)劃和二叉樹相結合，既考查了二叉樹的基本性質，又考查了大 家對動態(tài)規(guī)劃的掌握，不得不承認這是一道經(jīng)典好題。同樣，這道題最后要求輸出前序遍歷，只需 要用遞歸建樹即可，這里就不多說了。具體的預處理過程和動態(tài)規(guī)劃過程如下：/ 預處理read （n） ;For i: =1 to n doread （a i） ;For i:=0 to n doFor j:=0 to n doFi, j: =1;安陽一中信息學奧賽輔導資料For i:=l to n doFi, i:=ai;/DP 過程For i:=2 to n doFor j:=l to n-i+l doFor k:=j to i+j-1 doif fj, i+j-1fj,k-1*fk+1, i+j-