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

1、區(qū)間類動態(tài)規(guī)劃區(qū)間類動態(tài)規(guī)劃合并類動態(tài)規(guī)劃的特點(diǎn)合并類動態(tài)規(guī)劃的特點(diǎn) 合并：意思就是將兩個或多個部分進(jìn)行整合，當(dāng)合并：意思就是將兩個或多個部分進(jìn)行整合，當(dāng)然也可以反過來，也就是是將一個問題進(jìn)行分解然也可以反過來，也就是是將一個問題進(jìn)行分解成兩個或多個部分。成兩個或多個部分。 特征：能將問題分解成為兩兩合并的形式特征：能將問題分解成為兩兩合并的形式 求解：對整個問題設(shè)最優(yōu)值，枚舉合并點(diǎn)，將問求解：對整個問題設(shè)最優(yōu)值，枚舉合并點(diǎn)，將問題分解成為左右兩個部分，最后將左右兩個部分題分解成為左右兩個部分，最后將左右兩個部分的最優(yōu)值進(jìn)行合并得到原問題的最優(yōu)值。有點(diǎn)類的最優(yōu)值進(jìn)行合并得到原問題的最優(yōu)值。有點(diǎn)

2、類似分治算法的解題思想。似分治算法的解題思想。 典型試題：整數(shù)劃分，凸多邊形劃分、石子合并典型試題：整數(shù)劃分，凸多邊形劃分、石子合并、多邊形合并、能量項(xiàng)鏈等。、多邊形合并、能量項(xiàng)鏈等。整數(shù)劃分整數(shù)劃分 給出一個長度為給出一個長度為n的數(shù)的數(shù) 要在其中加要在其中加m-1個乘號，分成個乘號，分成m段段 這這m段的乘積之和最大段的乘積之和最大 mn=20 有有T組數(shù)據(jù)，組數(shù)據(jù)，T=10000貪心法貪心法 盡可能平均分配各段，這樣最終的數(shù)值將會盡可能大。但盡可能平均分配各段，這樣最終的數(shù)值將會盡可能大。但有反例。如有反例。如191919分成分成3段段 19*19*19=6859但但191*91*9=1

3、56429，顯然乘積更大。，顯然乘積更大。 將一個數(shù)分成若干段乘積后比該數(shù)小，因?yàn)檩斎霐?shù)不超過將一個數(shù)分成若干段乘積后比該數(shù)小，因?yàn)檩斎霐?shù)不超過20位，因此不需高精度運(yùn)算。位，因此不需高精度運(yùn)算。 證明：證明： 假設(shè)假設(shè)AB分成分成A和和B,且且A,BA*B(相當(dāng)于相當(dāng)于B個個A相加相加) 同理可證明同理可證明A,B為任意位也成立為任意位也成立動態(tài)規(guī)劃動態(tài)規(guī)劃 可以先預(yù)處理出原數(shù)第可以先預(yù)處理出原數(shù)第i到到j(luò)段的數(shù)值段的數(shù)值A(chǔ)i,j是多少，是多少，這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。 Fi，j表示把這個數(shù)前表示把這個數(shù)前i位分成位分成j段得到

4、的最大乘積。段得到的最大乘積。 Fi,j=Fk,j-1*Ak+1,i, 1ki=n, j=m 時間復(fù)雜度為時間復(fù)雜度為Omn2 由于有由于有10000組數(shù)據(jù)，因此估計(jì)時間復(fù)雜度為組數(shù)據(jù)，因此估計(jì)時間復(fù)雜度為10000*203=8*107 至于說輸出，記錄轉(zhuǎn)移的父親就可以了。至于說輸出，記錄轉(zhuǎn)移的父親就可以了。石子合并 l 在一園形操場四周擺放在一園形操場四周擺放N堆石子堆石子(N100)；l 現(xiàn)要將石子有次序地合并成一堆；現(xiàn)要將石子有次序地合并成一堆；l 規(guī)定每次只能選相臨的兩堆合并成一堆規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的并將新的一堆的石子數(shù)一堆的石子數(shù),記為該次合并的得分。記為該次

5、合并的得分。l 選擇一種合并石子的方案選擇一種合并石子的方案,使得做使得做N-1次合并次合并,得分得分的總和最少的總和最少 l 選擇一種合并石子的方案選擇一種合并石子的方案,使得做使得做N-1次合并次合并,得分得分的總和最大的總和最大例如貪心法 分析 假設(shè)只有假設(shè)只有2堆石子，顯然只有堆石子，顯然只有1種合并方案種合并方案 如果有如果有3堆石子，則有堆石子，則有2種合并方案，種合并方案，(1,2),3)和和(1,(2,3) 如果有如果有k堆石子呢？堆石子呢？ 不管怎么合并，總之最后總會歸結(jié)為不管怎么合并，總之最后總會歸結(jié)為2堆，如果我們把最堆，如果我們把最后兩堆分開，左邊和右邊無論怎么合并，都

6、必須滿足最優(yōu)后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)合并方案，整個問題才能得到最優(yōu)解。如下圖：合并方案，整個問題才能得到最優(yōu)解。如下圖：動態(tài)規(guī)劃動態(tài)規(guī)劃 設(shè)設(shè)ti,j表示從第表示從第i堆到第堆到第j堆石子數(shù)總和。堆石子數(shù)總和。Fmax(i,j)表示將從第表示將從第i堆石子合并到第堆石子合并到第j堆石子的最大的堆石子的最大的得分得分Fmin(i,j)表示將從第表示將從第i堆石子合并到第堆石子合并到第j堆石子的最小的堆石子的最小的得分得分 同理，同理， Fmaxi,i = 0，F(xiàn)mini,i = 0 時間復(fù)雜度為時間復(fù)雜度為O(n3),), 1max(),max(),max(max1ji

7、tjkFkiFjiFjki,), 1min(),min(),min(min1jitjkFkiFjiFjki優(yōu)化 由于石子堆是一個圈，因此我們可以枚舉分開的位置，首由于石子堆是一個圈，因此我們可以枚舉分開的位置，首先將這個圈轉(zhuǎn)化為鏈，因此總的時間復(fù)雜度為先將這個圈轉(zhuǎn)化為鏈，因此總的時間復(fù)雜度為O(n4)。 這樣顯然很高，其實(shí)我們可以將這條鏈延長這樣顯然很高，其實(shí)我們可以將這條鏈延長2倍，擴(kuò)展成倍，擴(kuò)展成2n-1堆，其中第堆，其中第1堆與堆與n+1堆完全相同，第堆完全相同，第i堆與堆與n+i堆完全堆完全相同，這樣我們只要對這相同，這樣我們只要對這2n堆動態(tài)規(guī)劃后，枚舉堆動態(tài)規(guī)劃后，枚舉f(1,n)

8、,f(2,n+1),f(n,2n-1)取最優(yōu)值即可即可。取最優(yōu)值即可即可。 時間復(fù)雜度為時間復(fù)雜度為O(8n3),如下圖：如下圖：猜測猜測 合并第合并第i堆到第堆到第j堆石子的最優(yōu)斷開位置堆石子的最優(yōu)斷開位置si,j要么等要么等于于i+1，要么等于，要么等于j-1，也就是說最優(yōu)合并方案只可，也就是說最優(yōu)合并方案只可能是：能是： (i) (i+1 j) 或者或者 (i j-1) (j) 證明 設(shè)合并第設(shè)合并第i堆到第堆到第j堆石子的斷開位置堆石子的斷開位置 p，且，且ipj-1。設(shè)在。設(shè)在i,p之間存在一種斷開方案之間存在一種斷開方案q。如下圖；。如下圖； 情況情況1：ti, ptp+1,j 合

9、并方案合并方案1： (iq) (q+1.p) (p+1j) ，它的得分，它的得分 : F1=Fmax(i, q)+Fmax(q+1,p)+Fmax(p+1,j)+ti, j+ti, p合并方案合并方案2: (iq) (q+1.p) (p+1j) ，它的得分，它的得分： F2 = Fmax i, q+Fmax q+1,p+Fmax p+1,j+ti, j+tq+1,j由于由于qp，所以，所以ti, ptp+1,jtq+1,j，所以，所以F1tp+1,j 與情況與情況1是對稱。（證明略）是對稱。（證明略）狀態(tài)轉(zhuǎn)移方程 設(shè)設(shè)ti,j表示從第表示從第i堆到第堆到第j堆石子數(shù)總和。堆石子數(shù)總和。Fmax

10、(i,j)表示將從第表示將從第i堆石子合并到第堆石子合并到第j堆石子的最大的堆石子的最大的得分得分Fmin(i,j)表示將從第表示將從第i堆石子合并到第堆石子合并到第j堆石子的最小的堆石子的最小的得分得分 同理，同理， Fmaxi,i = 0，F(xiàn)mini,i = 0 時間復(fù)雜度為時間復(fù)雜度為O(n2),)1,max(), 1max(),max(maxjitjiFjiFjiF,)1,min(), 1min(),min(minjitjiFjiFjiF能量項(xiàng)鏈能量項(xiàng)鏈 在在Mars星球上，每個星球上，每個Mars人都隨身佩帶著一串能量項(xiàng)鏈。人都隨身佩帶著一串能量項(xiàng)鏈。 在項(xiàng)鏈上有在項(xiàng)鏈上有N顆能量珠

11、。顆能量珠。 能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。某個正整數(shù)。 對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。如果前一顆能量珠的頭標(biāo)記為顆珠子的頭標(biāo)記。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)，尾標(biāo)記為記為r，后一顆能量珠的頭標(biāo)記為，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為，尾標(biāo)記為n，則聚合后，則聚合后釋放的能量為釋放的能量為mrnMars單位），新產(chǎn)生的珠子的頭單位），新產(chǎn)生的珠子的頭標(biāo)記為標(biāo)記為m，尾標(biāo)記為，尾標(biāo)記為n。 顯然，對于一串項(xiàng)鏈不同的聚合順序得

12、到的總能量是不同顯然，對于一串項(xiàng)鏈不同的聚合順序得到的總能量是不同的，請你設(shè)計(jì)一個聚合順序，使一串項(xiàng)鏈釋放出的總能量的，請你設(shè)計(jì)一個聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。最大。 分析樣例：分析樣例：N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。 我們用記號我們用記號 表示兩顆珠子的聚合操作，釋放總能量：表示兩顆珠子的聚合操作，釋放總能量：(4 1) 2) 3）=10*2*3+10*3*5+10*5*10=710動態(tài)規(guī)劃 該題與石子合并完全類似。該題與石子合并完全類似。 設(shè)鏈中的第設(shè)鏈中的第i顆珠子頭尾標(biāo)記為顆珠子頭尾標(biāo)記

13、為(Si-1與與Si)。 令令F(i,j)表示從第表示從第i顆珠子一直合并到第顆珠子一直合并到第j顆珠子所能顆珠子所能產(chǎn)生的最大能量，則有：產(chǎn)生的最大能量，則有：F(i,j)=MaxF(i,k)+F(k+1,j)+Si-1*Sk*Sj, i=kj 邊界條件：邊界條件：F(i,i)=0 1=ikj=n 至于圈的處理，與石子合并方法完全相同，時間至于圈的處理，與石子合并方法完全相同，時間復(fù)雜度復(fù)雜度O(8n3) 。凸多邊形的三角剖分凸多邊形的三角剖分 給定由給定由N頂點(diǎn)組成的凸多邊形頂點(diǎn)組成的凸多邊形 每個頂點(diǎn)具有權(quán)值每個頂點(diǎn)具有權(quán)值 將凸將凸N邊形剖分成邊形剖分成N-2個三角形個三角形 求求N-

14、2個三角形頂點(diǎn)權(quán)值乘積之和最?。總€三角形頂點(diǎn)權(quán)值乘積之和最??？ 樣例樣例 上述凸五邊形分成上述凸五邊形分成123 ， ， 345 三角形頂點(diǎn)權(quán)值乘積之和為：三角形頂點(diǎn)權(quán)值乘積之和為： 121*122*123+121*123*231+123*245*231= 12214884分析性質(zhì)：一個凸多邊形剖分一個三角形后，可以將性質(zhì)：一個凸多邊形剖分一個三角形后，可以將凸多邊形剖分成三個部分：凸多邊形剖分成三個部分：一個三角形一個三角形二個凸多邊形圖二個凸多邊形圖2可以看成另一個凸多邊形為可以看成另一個凸多邊形為0）動態(tài)規(guī)劃 如果我們按順時針將頂點(diǎn)編號，則可以相鄰兩個頂點(diǎn)描如果我們按順時針將頂點(diǎn)編號，則

15、可以相鄰兩個頂點(diǎn)描述一個凸多邊形。述一個凸多邊形。 設(shè)設(shè)f(i,j)表示表示ij這一段連續(xù)頂點(diǎn)的多邊形劃分后最小乘積這一段連續(xù)頂點(diǎn)的多邊形劃分后最小乘積 枚舉點(diǎn)枚舉點(diǎn)k，i、j和和k相連成基本三角形，并把原多邊形劃分相連成基本三角形，并把原多邊形劃分成兩個子多邊形，則有成兩個子多邊形，則有 f(i,j)=minf(i,k)+f(k,j)+ai*aj*ak 1=ikj=n 時間復(fù)雜度時間復(fù)雜度O(n3)討論為什么可以不考慮這種情況？為什么可以不考慮這種情況？ 可以看出圖可以看出圖1和圖和圖2是等價(jià)的，也就是說如果是等價(jià)的，也就是說如果存在圖存在圖1的剖分方案，則可以轉(zhuǎn)化成圖的剖分方案，則可以轉(zhuǎn)化

16、成圖2的剖的剖分方案，因此可以不考慮圖分方案，因此可以不考慮圖1的這種情形。的這種情形。多邊形多邊形IOI98IOI98） 多角形是一個單人玩的游戲，開始時多角形是一個單人玩的游戲，開始時有一個有一個N N個頂點(diǎn)的多邊形。如圖，這個頂點(diǎn)的多邊形。如圖，這里里N=4N=4。每個頂點(diǎn)有一個整數(shù)標(biāo)記，。每個頂點(diǎn)有一個整數(shù)標(biāo)記，每條邊上有一個每條邊上有一個“+”“+”號或號或“* *”號。號。邊從邊從1 1編號到編號到N N。 第一步，一條邊被拿走；隨后各步第一步，一條邊被拿走；隨后各步包括如下：包括如下： 選擇一條邊選擇一條邊E E和連接著和連接著E E的兩個頂點(diǎn)的兩個頂點(diǎn)V1V1和和 V2 V2；

17、 得到一個新的頂點(diǎn)，標(biāo)記為得到一個新的頂點(diǎn)，標(biāo)記為V1V1與與V2V2通通過邊過邊E E上的運(yùn)算符運(yùn)算的結(jié)果。上的運(yùn)算符運(yùn)算的結(jié)果。 最后，游戲中沒有邊，游戲的得分為最后，游戲中沒有邊，游戲的得分為僅剩余的一個頂點(diǎn)的值。僅剩余的一個頂點(diǎn)的值。 -7425+*1234+*樣例分析 分析 我們先枚舉第一次刪掉的邊，然后再對每種狀態(tài)進(jìn)行動態(tài)規(guī)劃求最大值 。 用f(i,j)表示從點(diǎn)i到點(diǎn)j進(jìn)行刪邊操作所能得到的最大值，num(i)表示第i個頂點(diǎn)上的數(shù)，若為加法，那么：)(), i (),(),(max),(11inumifkikjfikfjifik進(jìn)一步分析 最后，我們允許頂點(diǎn)上出現(xiàn)負(fù)數(shù)。以前的方程還

18、適不適最后，我們允許頂點(diǎn)上出現(xiàn)負(fù)數(shù)。以前的方程還適不適用呢？用呢？ 這個例子的最優(yōu)解應(yīng)該是這個例子的最優(yōu)解應(yīng)該是3+23+2）* *（-10-10）* *（-5-5）=250=250，然而如果沿用以前的方程，得出的解將是（，然而如果沿用以前的方程，得出的解將是（-10-10）* *3+23+2）* *（-5-5）=125=125。為什么？。為什么？ 我們發(fā)現(xiàn)，兩個負(fù)數(shù)的積為正數(shù)；這兩個負(fù)數(shù)越小，它我們發(fā)現(xiàn)，兩個負(fù)數(shù)的積為正數(shù)；這兩個負(fù)數(shù)越小，它們的積越大。我們從前的方程，只是盡量使得局部解最們的積越大。我們從前的方程，只是盡量使得局部解最大，而從來沒有想過負(fù)數(shù)的積為正數(shù)這個問題。大，而從來沒有

19、想過負(fù)數(shù)的積為正數(shù)這個問題。 -1032-5*圖六+分析分析 對于加法，兩個最優(yōu)相加肯定最優(yōu)，而對于乘法對于加法，兩個最優(yōu)相加肯定最優(yōu)，而對于乘法 求最大值：求最大值： 正數(shù)正數(shù)，如果兩個都是最大值，則結(jié)果最大正數(shù)正數(shù)，如果兩個都是最大值，則結(jié)果最大 正數(shù)負(fù)數(shù)，正數(shù)最小，負(fù)數(shù)最大，則結(jié)果最大正數(shù)負(fù)數(shù)，正數(shù)最小，負(fù)數(shù)最大，則結(jié)果最大 負(fù)數(shù)負(fù)數(shù)，如果兩個都是最小值，則結(jié)果最大負(fù)數(shù)負(fù)數(shù)，如果兩個都是最小值，則結(jié)果最大 求最小值：求最小值： 正數(shù)正數(shù)，如果兩個都是最小值，則結(jié)果最小正數(shù)正數(shù)，如果兩個都是最小值，則結(jié)果最小 正數(shù)負(fù)數(shù)，正數(shù)最大，負(fù)數(shù)最小，則結(jié)果最小正數(shù)負(fù)數(shù)，正數(shù)最大，負(fù)數(shù)最小，則結(jié)果最小

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

21、k)+fmin(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j), 1min(*),(fmin), 1max(*),(fmin), 1min(*),(fmax), 1max(*),(fmax),max(jkfkijkfkijkfkijkfkijif), 1max(*),(fmax), 1max(*),(fmin), 1min(*),(fmax), 1min(*),(fmin),min(jkfkijkfkijkfkijkfkijif當(dāng)當(dāng)OP=OP=* *完美解決 初始值初始值 Fmax(i,i)=num(i) Fmax(i,i)=num(i) Fmin(i,i)=

22、num(i) Fmin(i,i)=num(i) 1=i=k=j=n1=i=k=D2,只要證明只要證明d(1,3) +d(2,4)d(1,2)+d(3,4)連接兩邊，見圖連接兩邊，見圖3，由三角形的三邊關(guān)系定理即可證，由三角形的三邊關(guān)系定理即可證明。明。分析 結(jié)論：青蛙在結(jié)論：青蛙在1號結(jié)點(diǎn)只能跳到號結(jié)點(diǎn)只能跳到2號結(jié)點(diǎn)或者號結(jié)點(diǎn)或者n號結(jié)點(diǎn)。號結(jié)點(diǎn)。 如果青蛙跳到了如果青蛙跳到了2號結(jié)點(diǎn)，則問題轉(zhuǎn)化為：從號結(jié)點(diǎn)，則問題轉(zhuǎn)化為：從2出發(fā)，遍歷出發(fā)，遍歷2.n一次僅一次的最短距離。一次僅一次的最短距離。 如果青蛙跳到了如果青蛙跳到了n號結(jié)點(diǎn)，則問題轉(zhuǎn)化為：從號結(jié)點(diǎn)，則問題轉(zhuǎn)化為：從n出發(fā)，遍歷出發(fā)

23、，遍歷2.n一次僅一次的最短距離。一次僅一次的最短距離。 這實(shí)際上是遞歸的思維，把問題轉(zhuǎn)化為了本質(zhì)相同但規(guī)模這實(shí)際上是遞歸的思維，把問題轉(zhuǎn)化為了本質(zhì)相同但規(guī)模更小的子問題更小的子問題,如下圖。如下圖。動態(tài)規(guī)劃(1) f(s,L,0)表示從表示從s出發(fā)，遍歷出發(fā)，遍歷s.s+L-1一次且僅一次的最短距離一次且僅一次的最短距離;f(s, L,1)表示從表示從s+L-1出發(fā)，遍歷出發(fā)，遍歷s.s+L-1一次且僅一次的一次且僅一次的最短距離。狀態(tài)轉(zhuǎn)移方程為：最短距離。狀態(tài)轉(zhuǎn)移方程為： 狀態(tài)總數(shù)為狀態(tài)總數(shù)為n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為，狀態(tài)轉(zhuǎn)移的復(fù)雜度為O(1)，總的時間復(fù)雜，總的時間復(fù)雜度為度為O(n2)

24、。1,1,) 1 , 1, 11(1,1,)0 , 1, 1(min)0 ,(LsLssdistLsfsssdistLsfLsf跳到跳到2,2, 1) 1 , 1,(,1,)0 , 1,(min) 1 ,(LsLsLsdistLsfsLssdistLsfLsf跳到跳到動態(tài)規(guī)劃(2) F(i,j,0)表示還有表示還有ij號點(diǎn)沒訪問號點(diǎn)沒訪問,且青蛙停在且青蛙停在i的最小值的最小值F(i,j,1)表示還有表示還有ij號點(diǎn)沒訪問號點(diǎn)沒訪問,且青蛙停在且青蛙停在j的最小值的最小值 狀態(tài)總數(shù)為狀態(tài)總數(shù)為n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為，狀態(tài)轉(zhuǎn)移的復(fù)雜度為O(1)，總的時間復(fù)雜度，總的時間復(fù)雜度為為O(n2)。j

25、ijidistjifiiiidistjifjif跳到停在跳到停在,) 1 , 1(1,1,)0 , 1(min)0 ,(ijidistjifjjjdistjifjif，跳到停在，跳到停在j,)0 , 1-,(1j,1,) 1 , 1,(min) 1 ,(主程序for i:=1 to n do for j:=n downto i+1 do begin update(fi+1,j,0,fi,j,0+di,i+1); / 停在i,跳到i+1 update(fi+1,j,1,fi,j,0+di,j); / 停在i,跳到j(luò) update(fi,j-1,0,fi,j,1+di,j); / 停在j,跳到i

26、update(fi,j-1,1,fi,j,1+dj-1,j); / 停在j,跳到j(luò)-1 end;棋盤分割棋盤分割 將一個的棋盤進(jìn)行如下分割：將原棋盤割下一塊矩將一個的棋盤進(jìn)行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進(jìn)行每次切割都只能沿著棋盤格子的邊進(jìn)行)允許的分割方案允許的分割方案 不允許的分割方案不允許的分割方案義務(wù)：義務(wù)：棋盤上每一格有一個分值，

27、一塊矩形棋盤的總棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤按分為其所含各格分值之和。現(xiàn)在需要把棋盤按上述規(guī)則分割成上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋塊矩形棋盤，并使各矩形棋盤總分的均方差最小。盤總分的均方差最小。均方差均方差 ：算術(shù)平均值算術(shù)平均值 ：nxxnii21)(nxxnii1樣例 輸入輸入31 1 1 1 1 1 1 31 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 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3輸出輸出1.633均方差公式化簡均方差公式化簡2122122112211222122122112121)2()2()()(xxnxxnxxnxxnxnxxxxnnxxxxnxxnxxniiniiniiniiniiniiniiiniinii分析 由化簡后的均方差公式：由化簡后的均方差公式： 可知，均方差的平方為每格數(shù)的平方和除以可知，均方差的平方為每格數(shù)的平方和除以n，然，然后減去平均值的平方，而后者是一個已知數(shù)。后減去平均值的平方，而后者是一個已知數(shù)。 因此，在棋盤切割的各種方案中，只需使得每個棋因此，在棋盤切