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

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

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

4、最小值只要枚舉 i 的位置，使得 Fi+1 ， n+F1 ，i+S1-i+si+1n 的和最小即可。綜上所述，我們可以總結出狀態轉移方程：Fi ，J ： =rainFi ，k+Fk+1 ， j+Si ，k+Sk+1 ，j）狀態轉移數組 F 即代表從第 i 個數到第 j 個數相加的最小代價， s 數組為預處理好的從第 i 個數 到第 j 個數的和。核心代碼如下：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 。二、區間型動態規劃的具體應用例 1 ：問題描述給定一個具有 N(N50)個頂點(從1到N編號)的凸多邊形 ,每個頂點的權均已知。問如何把這個 凸多邊形劃分成 N-2 個互不相交的三角形 ,使得這些三角形頂點的權的乘積之和最小?輸入文件 :第一行頂點數 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題目解析這是一道很典型的區間類型動態規劃問題。設 FI,J(IJ) 表示從頂點 I 到頂點 J 的凸多邊形三角 剖分后所得到的最大乘積 ,我們可以得到下面的動態轉移方程 :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;/ 數據賦初值for jj:=2 to n-1 do/枚舉多邊形邊數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) ，現要將石子有次序地合并成一堆。規定每次 只能選取相鄰的兩堆合并成新的一堆，并將新的一堆的石子數，記為該次合并的得分。編一程序， 由文件讀入堆棧數 N及每堆棧的石子數 (2

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

10、-8 -5 9-1 3 -9224 -5 -9 44 14 -4-4 -1 822這道題目可以說跟最小代價字母樹只有兩個不同的地方，一個是所求序列是一個環形的，另一 個是要求輸出方案。對于輸出方案而言，只需要用一般動態規劃記錄方案的方法即可，因為不是本 文的重點在此就不再深究。對于所求序列是環形的問題其實只需要用一個小小的技巧便輕松解決， 請先看代碼：/ 預處理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 從代碼中可以看出，這道題的寫法跟最小代價字母樹的區別在于權舉起點的時候長度增加到了2*n ，并且在最后求解的時候也需要枚舉起點，求長度為n 的最小值，這恰恰是利用了區間型動態

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

13、 +subtree 的根的分數 若某個子樹為空，規定其加分為 l ，葉子的加分就是葉結點本身的分數。不考慮它的空子樹。 試求一棵符合中序遍歷為 （1 ，2，3，n） 且加分最高的二叉樹 tree 。要求輸出：（1）tree 的最高加分（2）tree 的前序遍歷【輸入格式】第 1 行：一個整數 n（n30） ，為節點個數。第 2 行： n 個用空格隔開的整數，為每個節點的分數（ 分數 100） 。【輸出格式】第 1 行：一個整數，為最高加分 （結果不會超過 4，000，000，000） 。第 2 行： rl 個用空格隔開的整數，為該樹的前序遍歷。【輸入樣例】55 7 1 2 1 0 【輸出樣例】

14、1453 1 2 4 5 這道題目巧妙地將區間型動態規劃和二叉樹相結合，既考查了二叉樹的基本性質，又考查了大 家對動態規劃的掌握，不得不承認這是一道經典好題。同樣，這道題最后要求輸出前序遍歷，只需 要用遞歸建樹即可，這里就不多說了。具體的預處理過程和動態規劃過程如下：/ 預處理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-