1、區(qū)間動(dòng)態(tài)規(guī)劃（合并、剖分型）例3：給定一個(gè)具有N（N50）個(gè)頂點(diǎn)（從1到N編號(hào)）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問如何把這個(gè)凸多邊形劃分成N-2個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之和最??？輸入文件：第一行 頂點(diǎn)數(shù)N 第二行 N個(gè)頂點(diǎn)（從1到N）的權(quán)值輸出格式：最小的和的值 各三角形組成的方式輸入示例：5122 123 245 231 輸出示例：The minimum is ：12214884 The formation of 3 triangle: 3 4 5, 1 5 3, 1 2 3 【分析】設(shè)FI,J（IJ）表示從頂點(diǎn)I到頂點(diǎn)J的凸多邊形三角剖分后所得到的最大乘積，我們可以

2、得到下面的動(dòng)態(tài)轉(zhuǎn)移方程：FI,J=MinFI,K+FK,J+SI*SJ*SK (0IKJ=N)初始條件:F1，2=0目標(biāo)狀態(tài):F1,N但我們可以發(fā)現(xiàn),由于這里為乘積之和，在輸入數(shù)據(jù)較大時(shí)有可能超過長(zhǎng)整形范圍，所以還需用高精度計(jì)算 例6：石子合并 在一園形操場(chǎng)四周擺放N堆石子(N100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(20),(1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 (2) 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大輸入數(shù)據(jù): 第一行為石子

3、堆數(shù)N; 第二行為每堆石子數(shù),每?jī)蓚€(gè)數(shù)之間用一空格分隔.輸出數(shù)據(jù) :從第1至第N行為得分最小的合并方案. 第N+1行為空行.從N+2到2N+1行是得分最大的合并方案. N=5 石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24總分：62然而仔細(xì)琢磨后，發(fā)現(xiàn)更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24總分：

4、61顯然，貪心法是錯(cuò)誤的。動(dòng)態(tài)規(guī)劃用datai,j表示將從第i顆石子開始的接下來j顆石子合并所得的分值，maxi,j表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)maxi,1 = 0同樣的，我們用mini,j表示將第從第i顆石子開始的接下來j顆石子合并所得的最小值，可以得到類似的方程：mini,j = min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j)mini,0 = 0

5、這樣，我們完美地解決了這道題。時(shí)間復(fù)雜度也是O(n2)。例：添括號(hào)問題有一個(gè)由數(shù)字1，2，. ，9組成的數(shù)字串（長(zhǎng)度不超過200），問如何將M(M=20)個(gè)加號(hào)(+)插入到這個(gè)數(shù)字串中，使所形成的算術(shù)表達(dá)式的值最小。請(qǐng)編一個(gè)程序解決這個(gè)問題。注意：加號(hào)不能加在數(shù)字串的最前面或最末尾，也不應(yīng)有兩個(gè)或兩個(gè)以上的加號(hào)相鄰。M保證小于數(shù)字串的長(zhǎng)度。例如：數(shù)字串79846，若需要加入兩個(gè)加號(hào)，則最佳方案為79+8+46，算術(shù)表達(dá)式的值133。輸入格式從鍵盤讀入輸入文件名。數(shù)字串在輸入文件的第一行行首（數(shù)字串中間無空格且不折行），的值在輸入文件的第二行行首。輸出格式在屏幕上輸出所求得的最小和的精確值?！痉治觥靠紤]到數(shù)據(jù)的規(guī)模超過了長(zhǎng)整型,我們注意在解題過程中采用高精度算法.規(guī)劃方程:FI,J = MIN FI-1,K + NUMK+1,J (I-1=K=J-1)邊界值:F0,I := NUM1,I;FI，J表示前J個(gè)數(shù)字中添上I