合并類型動規(guī)

1、2022-6-132022-6-132 合并：意思就是將兩個或多個部分進行整合，當(dāng)然也可以反過來，也就是是將一個問題進行分解成兩個或多個部分。特征：能將問題分解成為兩兩合并的形式求解：對整個問題設(shè)最優(yōu)值，枚舉合并點，將問題分解成為左右兩個部分，最后將左右兩個部分的最優(yōu)值進行合并得到原問題的最優(yōu)值。有點類似分治算法的解題思想。典型試題：整數(shù)劃分，凸多邊形劃分、石子合并、多邊形合并、能量項鏈等。2022-6-133整數(shù)劃分如何把一個正整數(shù)N（N長度1）個部分，使這M個部分的乘積最大。N、M從鍵盤輸入，輸出最大值及一種劃分方式。輸入數(shù)據(jù)：第一行一個正整數(shù)T(T=10000)，表示有T組數(shù)據(jù)。接下來T

2、行每行兩個正整數(shù)N，M。輸出數(shù)據(jù)：對于每組數(shù)據(jù)第一行輸出最大值。第二行輸出劃分方案，將N按順序分成M個數(shù)輸出，兩個數(shù)之間用空格格開。樣例輸入文件：separate.in1199 2輸出文件：separate.out17119 92022-6-134 貪心法 盡可能平均分配各段，這樣最終的數(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為任意位也成立2022

3、-6-135 動態(tài)規(guī)劃 可以先預(yù)處理出原數(shù)第i到j(luò)段的數(shù)值A(chǔ)i,j是多少，這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。 Fi，j表示把這個數(shù)前i位分成j段得到的最大乘積。 Fi,j=Fk,j-1*Ak+1,i, 1ki=n, j=m 時間復(fù)雜度為Omn2 由于有10000組數(shù)據(jù)，因此估計時間復(fù)雜度為10000*203=8*107 至于說輸出，記錄轉(zhuǎn)移的父親就可以了。2022-6-136代碼program separate;const maxn=20;var v,f:array0.maxn,0.maxnof int64; g:array0.maxn,0.maxnof longint; t,m,i

4、,j,k,l:longint; n,sum:int64; s:string;function min(a,b:longint):longint;取a和b中的小值 begin if afi,j then begin fi,j:=fk-1,j-1*vk,i; gi,j:=k-1;記錄決策點 end; writeln(fl,m); print(l,m); writeln; end; close(input); close(output);end.2022-6-1310石子合并Description在一個圓形操場的四周擺放N堆石子(N100)，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并

5、成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。編一程序，讀入堆數(shù)N及每堆石子數(shù)(100)選擇一種合并石子的方案，分別得到合并這N堆石子為一堆，可以得到的最大得分和最小得分Input輸入包含多個例子。第一行為N，即石子堆的數(shù)目，以下一行為N個整形，分別代表每堆石子的數(shù)目。當(dāng)N=0時，輸入結(jié)束。Output對每個例子，輸出其最小得分和最大得分，這兩個數(shù)值以空格間隔開，每個例子占一行。2022-6-1311Sample Input630 35 15 5 10 2031 2 333363 4 5 6 7 80Sample Output275 4753339 667184 1252022-6-1

6、312 示例：如果石子對數(shù)為 4 4 5 92022-6-1313 貪心法 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 然而有更好的方案： 第一次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 顯然，貪心法是錯誤的。2022-6-1314 分析 假設(shè)只有2堆石子，顯然只有1種合

7、并方案 如果有3堆石子，則有2種合并方案，(1,2),3)和(1,(2,3) 如果有k堆石子呢？ 不管怎么合并，總之最后總會歸結(jié)為2堆，如果我們把最后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)合并方案，整個問題才能得到最優(yōu)解。如下圖：2022-6-1315 動態(tài)規(guī)劃 設(shè)ti,j表示從第i堆到第j堆石子數(shù)總和。 Fmax(i,j)表示將從第i堆石子合并到第j堆石子的最大的得分 Fmin(i,j)表示將從第i堆石子合并到第j堆石子的最小的得分 Fmaxi,i = 0，F(xiàn)mini,i = 0 時間復(fù)雜度為O(n3)2022-6-1316 優(yōu)化 由于石子堆是一個圈，因此我們可以枚舉分開的位置，首

8、先將這個圈轉(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)取最優(yōu)值即可即可。 時間復(fù)雜度為O(8n3),如下圖：2022-6-1317 猜想 合并第i堆到第j堆石子的最優(yōu)斷開位置si,j要么等于i+1，要么等于j-1，也就是說最優(yōu)合并方案：2022-6-13182022-6-1319 狀態(tài)轉(zhuǎn)移方程 設(shè)ti,j表示從第i堆到第j堆石子數(shù)總和。 Fmax(i,j)表示將從第i堆石子合并到第j堆石子的

9、最大的得分 Fmin(i,j)表示將從第i堆石子合并到第j堆石子的最小的得分Fmaxi,i = 0，F(xiàn)mini,i = 0時間復(fù)雜度為O(n2)2022-6-1320能量項鏈【問題描述】在 Mars 星球上，每個 Mars 人都隨身佩帶著一串能量項鏈。在項鏈上有 N 顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因為只有這樣，通過吸盤（吸盤是 Mars 人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為 m ，尾標(biāo)記為 r ，后一

10、顆能量珠的頭標(biāo)記為 r ，尾標(biāo)記為 n ，則聚合后釋放的能量為 （ Mars 單位），新產(chǎn)生的珠子的頭標(biāo)記為 m ，尾標(biāo)記為 n 。需要時， Mars 人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設(shè)計一個聚合順序，使一串項鏈釋放出的總能量最大。例如：設(shè) N=4 ， 4 顆珠子的頭標(biāo)記與尾標(biāo)記依次為 (2 ， 3) (3 ， 5) (5 ， 10) (10 ， 2) 。我們用記號 表示兩顆珠子的聚合操作， (j k) 表示第 j ， k 兩顆珠子聚合后所釋放的能量。則第 4 、 1 兩顆珠子聚合后釋放的能量為：(4

11、1)=10*2*3=60 。這一串項鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量 為(4 1) 2) 3 ） =10*2*3+10*3*5+10*5*10=710 。nrm2022-6-1321【輸入文件】 輸入文件 energy.in 的第一行是一個正整數(shù) N （ 4 N 100 ），表示項鏈上珠子的個數(shù)。第二行是 N 個用空格隔開的正整數(shù)，所有的數(shù)均不超過 1000 。第 i 個數(shù)為第 i 顆珠子的頭標(biāo)記（ 1 i N ），當(dāng) iN 時，第 i 顆珠子的尾標(biāo)記應(yīng)該等于第 i+1 顆珠子的頭標(biāo)記。第 N 顆珠子的尾標(biāo)記應(yīng)該等于第 1 顆珠子的頭標(biāo)記。 至于珠子的順序，你可以這樣確定：將項鏈放

12、到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。【輸出文件】 輸出文件 energy.out 只有一行，是一個正整數(shù) E （ E 2.1*10 9 ），為一個最優(yōu)聚合順序所釋放的總能量?！据斎胼敵鰳永縠nergy.in42 3 5 10energy.out7102022-6-1322 分析樣例： N=4，4顆珠子的頭標(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=7102022-6-1323 動態(tài)規(guī)劃 該題與石子合并完

13、全類似。 設(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)=0 1=ikj=n 至于圈的處理，與石子合并方法完全相同，時間復(fù)雜度O(8n3)。2022-6-1324varf:array1.200,1.200 of longint;a:array1.200,1.2 of longint;n,i,j,k,max,stt:longint;beginreadln(n);for i:=1 to n do read(ai

14、,1);for i:=1 to n-1 do ai,2:=ai+1,1;an,2:=a1,1;for i:=n+1 to 2*n do begin ai,1:=ai-n,1; ai,2:=ai-n,2;end;for j:=1 to n-1 do for i:=1 to 2*n-j do for k:=i to i+j-1 do begin stt:=fi,k+fk+1,i+j+ai,1+ak,2+ai+j,2; if fi,i+jmax then max:=fi,i+n-1;writeln(max);end.2022-6-1325凸多邊形的三角剖分給定一具有N個頂點（從1到N編號）的凸多邊形

15、，每個頂點的權(quán)均已知。問如何把這個凸多邊形劃分成N-2個互不相交的三角形，使得這些三角形頂點的權(quán)的乘積之和最?。枯斎霐?shù)據(jù)：第一行 頂點數(shù)N（N50）。第二行 N個頂點（從1到N）的權(quán)值，權(quán)值為小于32768的整數(shù)。輸出數(shù)據(jù)：第一行為各三角形頂點的權(quán)的乘積之和最小值。樣例division.in5121 122 123 245 231division.out122148842022-6-1326 樣例分析 上述凸五邊形分成123 ，135，345 三角形頂點權(quán)值乘積之和為： 121*122*123+121*123*231+123*245*231= 122148842022-6-1327 分析性質(zhì)：

16、一個凸多邊形剖分一個三角形后，可以將凸多邊形剖分成三個部分：一個三角形二個凸多邊形（圖2可以看成另一個凸多邊形為0）2022-6-1328 動態(tài)規(guī)劃 如果我們按順時針將頂點編號，則可以相鄰兩個頂點描述一個凸多邊形。 設(shè)f(i,j)表示ij這一段連續(xù)頂點的多邊形劃分后最小乘積 枚舉點k，i、j和k相連成基本三角形，并把原多邊形劃分成兩個子多邊形，則有 f(i,j)=minf(i,k)+f(k,j)+ai*aj*ak 1=ikj=n 時間復(fù)雜度O(n3)2022-6-1329 討論為什么可以不考慮這種情況？2022-6-1330 可以看出圖1和圖2是等價的，也就是說如果存在圖1的剖分方案，則可以轉(zhuǎn)

17、化成圖2的剖分方案，因此可以不考慮圖1的這種情形。2022-6-1331青蛙的煩惱池塘中有n片荷葉恰好圍成了一個凸多邊形，有一只小青蛙恰好站在1號荷葉上，小青蛙想通過最短的路程遍歷所有的荷葉（經(jīng)過一個荷葉一次且僅一次），小青蛙可以從一片荷葉上跳到另外任意一片荷葉上。輸入數(shù)據(jù)(frog.in)第一行為整數(shù)n，荷葉的數(shù)量。接下來n行，每行兩個實數(shù)，為n個多邊形的頂點坐標(biāo)，按照順時針方向給出。保證不會爆double。輸出數(shù)據(jù)(frog.out)：遍歷所有荷葉最短路程，請保留3位小數(shù)。樣例輸入:frog.in450.0 1.05.0 1.00.0 0.045.0 0.0輸出:frog.out50.21

18、1數(shù)據(jù)范圍：對于所有數(shù)據(jù),0nD2,只要證明d(1,3) +d(2,4)d(1,2)+d(3,4)連接兩邊，見圖3，由三角形的三邊關(guān)系定理即可證明。2022-6-1334 結(jié)論：青蛙在1號結(jié)點只能跳到2號結(jié)點或者n號結(jié)點。 如果青蛙跳到了2號結(jié)點，則問題轉(zhuǎn)化為：從2出發(fā)，遍歷2.n一次僅一次的最短距離。 如果青蛙跳到了n號結(jié)點，則問題轉(zhuǎn)化為：從n出發(fā)，遍歷2.n一次僅一次的最短距離。 這實際上是遞歸的思維，把問題轉(zhuǎn)化為了本質(zhì)相同但規(guī)模更小的子問題,如下圖。2022-6-1335 動態(tài)規(guī)劃(1) f(s,L,0)表示從s出發(fā)，遍歷s.s+L-1一次且僅一次的最短距離; f(s, L,1)表示從s

19、+L-1出發(fā)，遍歷s.s+L-1一次且僅一次的最短距離。狀態(tài)轉(zhuǎn)移方程為： 狀態(tài)總數(shù)為n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為O(1)，總的時間復(fù)雜度為O(n2)。2022-6-1336 動態(tài)規(guī)劃(2) F(i,j,0)表示還有ij號點沒訪問,且青蛙停在i的最小值 F(i,j,1)表示還有ij號點沒訪問,且青蛙停在j的最小值 狀態(tài)總數(shù)為n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為O(1)，總的時間復(fù)雜度為O(n2)。2022-6-1337 主程序 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 upd

20、ate(fi+1,j,1,fi,j,0+di,j); / 停在i,跳到j(luò) update(fi,j-1,0,fi,j,1+di,j); / 停在j,跳到i update(fi,j-1,1,fi,j,1+dj-1,j); / 停在j,跳到j(luò)-1 end;2022-6-1338棋盤分割 將一個*的棋盤進行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進行) 原棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差最小。均方差2022-6-1339 xi為第i塊矩形棋盤的總分。 請編程對給出的棋盤及n，求出O的最小值2022-6-1340Input 第1行為一個整數(shù)n(1 n 15)。 第2行至第9行