區(qū)間型動態(tài)規(guī)劃

1、區(qū)間類動態(tài)規(guī)劃長沙市雅禮中學(xué) 朱全民整數(shù)劃分給出一個長度為n的數(shù)要在其中加m-1個乘號，分成m段這m段的乘積之和最大mn=20有T組數(shù)據(jù)，T=10000貪心法盡可能平均分配各段，這樣最終的數(shù)值將會盡可能大。但有反例。如191919分成3段 19*19*19=6859但191*91*9=156429，顯然乘積更大。將一個數(shù)分成若干段乘積后比該數(shù)小，因為輸入數(shù)不超過20位，因此不需高精度運算。證明：假設(shè)AB分成A和B,且A,BA*B(相當(dāng)于B個A相加)同理可證明A,B為任意位也成立動態(tài)規(guī)劃可以先預(yù)處理出原數(shù)第i到j(luò)段的數(shù)值A(chǔ)i,j是多少，這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。Fi，j表示把這

2、個數(shù)前i位分成j段得到的最大乘積。Fi,j=Fk,j-1*Ak+1,i,1ki=n, j=m 時間復(fù)雜度為Om2n由于有10000組數(shù)據(jù)，因此估計時間復(fù)雜度為10000*203=8*107至于說輸出，記錄轉(zhuǎn)移的父親就可以了。石子合并 在一園形操場四周擺放N堆石子(N100)；現(xiàn)要將石子有次序地合并成一堆；規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大示例貪心法 N=5 石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過程如下：第一次 3 4 6

3、 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24總分：62然而有更好的方案：第一次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總分：61顯然，貪心法是錯誤的。 分析假設(shè)只有2堆石子，顯然只有1種合并方案如果有3堆石子，則有2種合并方案，(1,2),3)和(1,(2,3)如果有k堆石子呢？不管怎么合并，總之最后總會歸結(jié)為2堆，如果我們把最后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)合并方案，整

4、個問題才能得到最優(yōu)解。如下圖：動態(tài)規(guī)劃 設(shè)ti,j表示從第i堆到第j堆石子數(shù)總和。Fmax(i,j)表示將從第i堆石子合并到第j堆石子的最大的得分Fmin(i,j)表示將從第i堆石子合并到第j堆石子的最小的得分同理，F(xiàn)maxi,i = 0，F(xiàn)mini,i = 0時間復(fù)雜度為O(n3)優(yōu)化由于石子堆是一個圈，因此我們可以枚舉分開的位置，首先將這個圈轉(zhuǎn)化為鏈，因此總的時間復(fù)雜度為O(n4)。這樣顯然很高，其實我們可以將這條鏈延長2倍，擴展成2n-1堆，其中第1堆與n+1堆完全相同，第i堆與n+i堆完全相同，這樣我們只要對這2n堆動態(tài)規(guī)劃后，枚舉f(1,n),f(2,n+1),f(n,2n-1)取最

5、優(yōu)值即可即可。時間復(fù)雜度為O(8n3),如下圖：能量項鏈在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為mrn（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。顯然，對于一串項鏈不同的聚合順序得到的總能量是不同的，請你設(shè)計一個聚合順序，使一串項鏈釋放出的總能量最大。分析樣例：N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5

6、) (5，10) (10，2)。我們用記號表示兩顆珠子的聚合操作，釋放總能量：(41)2)3）=10*2*3+10*3*5+10*5*10=710動態(tài)規(guī)劃該題與石子合并完全類似。設(shè)鏈中的第i顆珠子頭尾標(biāo)記為(Si-1與Si)。令F(i,j)表示從第i顆珠子一直合并到第j顆珠子所能產(chǎn)生的最大能量，則有：F(i,j)=MaxF(i,k)+F(k+1,j)+Si-1*Sk*Sj, i=kj邊界條件：F(i,i)=01=ikj=n至于圈的處理，與石子合并方法完全相同，時間復(fù)雜度O(8n3) 。凸多邊形的三角剖分給定由N頂點組成的凸多邊形每個頂點具有權(quán)值將凸N邊形剖分成N-2個三角形求N-2個三角形頂點

7、權(quán)值乘積之和最??？樣例上述凸五邊形分成123 ， 135， 345三角形頂點權(quán)值乘積之和為：121*122*123+121*123*231+123*245*231= 12214884分析性質(zhì)：一個凸多邊形剖分一個三角形后，可以將凸多邊形剖分成三個部分：一個三角形二個凸多邊形（圖2可以看成另一個凸多邊形為0）動態(tài)規(guī)劃如果我們按順時針將頂點編號，則可以相鄰兩個頂點描述一個凸多邊形。設(shè)f(i,j)表示ij這一段連續(xù)頂點的多邊形劃分后最小乘積枚舉點k，i、j和k相連成基本三角形，并把原多邊形劃分成兩個子多邊形，則有f(i,j)=minf(i,k)+f(k,j)+ai*aj*ak1=ikj=n時間復(fù)雜度

8、O(n3)討論為什么可以不考慮這種情況？可以看出圖1和圖2是等價的，也就是說如果存在圖1的剖分方案，則可以轉(zhuǎn)化成圖2的剖分方案，因此可以不考慮圖1的這種情形。多邊形（IOI98） 多角形是一個單人玩的游戲，開始時有一個N個頂點的多邊形。如圖，這里N=4。每個頂點有一個整數(shù)標(biāo)記，每條邊上有一個“+”號或“*”號。邊從1編號到N。 第一步，一條邊被拿走；隨后各步包括如下：選擇一條邊E和連接著E的兩個頂點V1和 V2；得到一個新的頂點，標(biāo)記為V1與V2通過邊E上的運算符運算的結(jié)果。最后，游戲中沒有邊，游戲的得分為僅剩余的一個頂點的值。 樣例分析 分析我們先枚舉第一次刪掉的邊，然后再對每種狀態(tài)進行動態(tài)

9、規(guī)劃求最大值 。用f(i,j)表示從點i到點j進行刪邊操作所能得到的最大值，num(i)表示第i個頂點上的數(shù)，若為加法，那么：進一步分析最后，我們允許頂點上出現(xiàn)負(fù)數(shù)。以前的方程還適不適用呢？這個例子的最優(yōu)解應(yīng)該是（3+2）*（-10）*（-5）=250，然而如果沿用以前的方程，得出的解將是（-10）*3+2）*（-5）=125。為什么？我們發(fā)現(xiàn)，兩個負(fù)數(shù)的積為正數(shù)；這兩個負(fù)數(shù)越小，它們的積越大。我們從前的方程，只是盡量使得局部解最大，而從來沒有想過負(fù)數(shù)的積為正數(shù)這個問題。 -1032-5*圖六+分析對于加法，兩個最優(yōu)相加肯定最優(yōu)，而對于乘法求最大值：正數(shù)正數(shù)，如果兩個都是最大值，則結(jié)果最大正數(shù)

10、負(fù)數(shù)，正數(shù)最小，負(fù)數(shù)最大，則結(jié)果最大負(fù)數(shù)負(fù)數(shù)，如果兩個都是最小值，則結(jié)果最大求最小值：正數(shù)正數(shù)，如果兩個都是最小值，則結(jié)果最小正數(shù)負(fù)數(shù)，正數(shù)最大，負(fù)數(shù)最小，則結(jié)果最小負(fù)數(shù)負(fù)數(shù)，如果兩個都是最大值，則結(jié)果最小最終？我們引入函數(shù)fmin和fmax來解決這個問題。fmax(i,j) 表示從點i開始，到但j為止進行刪邊操作所能得到的最大值，fmin(i,j) 表示最小值。當(dāng)OP=+Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j)當(dāng)OP=*完美解決初始值 Fmax(i,i)=num(i) Fmin(i,i)=num(

11、i)1=i=k=j=n空間復(fù)雜度:O(n2) 時間復(fù)雜度:先要枚舉每一條邊為O(n)，然后動態(tài)規(guī)劃為O(n3 )，因此總為O(n4)。棋盤分割 將一個的棋盤進行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進行)允許的分割方案 不允許的分割方案任務(wù)：棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差最小。均方差 ：算術(shù)平均值 ：樣例 輸入31 1 1 1 1 1 1 31 1 1

12、 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3輸出1.633均方差公式化簡分析 由化簡后的均方差公式：可知，均方差的平方為每格數(shù)的平方和除以n，然后減去平均值的平方，而后者是一個已知數(shù)。因此，在棋盤切割的各種方案中，只需使得每個棋盤內(nèi)各數(shù)值的平方和最小即可。因此，我們需要求出各棋盤分割后的每個棋盤各數(shù)平方和的最小值，設(shè)為w，那么答案為：棋盤切割后的四種情況動態(tài)規(guī)劃設(shè)F(i,x1,y1,x2,y2)表示以x1,y1x2,y2為四邊形對角線的棋盤切割成k塊的各塊數(shù)值總平方和的最小值，則有：1=X1,x2,x3,x4=8,1=i=n。設(shè)棋盤邊長為m,則狀態(tài)數(shù)為nm4 ,決策數(shù)最多m。先預(yù)處理從左上角(1,1)到右下角(i,j)的棋盤和時間復(fù)雜度為O(m2)，因此轉(zhuǎn)移為O(1),總時間復(fù)雜度為O(nm5)。總結(jié)該類