合并類(lèi)型動(dòng)規(guī)

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

2、行每行兩個(gè)正整數(shù)N，M。輸出數(shù)據(jù)：對(duì)于每組數(shù)據(jù)第一行輸出最大值。第二行輸出劃分方案，將N按順序分成M個(gè)數(shù)輸出，兩個(gè)數(shù)之間用空格格開(kāi)。樣例輸入文件：separate.in1199 2輸出文件：separate.out17119 92022-6-134 貪心法 盡可能平均分配各段，這樣最終的數(shù)值將會(huì)盡可能大。但有反例。如191919分成3段 19*19*19=6859 但191*91*9=156429，顯然乘積更大。 將一個(gè)數(shù)分成若干段乘積后比該數(shù)小，因?yàn)檩斎霐?shù)不超過(guò)20位，因此不需高精度運(yùn)算。 證明： 假設(shè)AB分成A和B,且A,BA*B(相當(dāng)于B個(gè)A相加) 同理可證明A,B為任意位也成立2022

3、-6-135 動(dòng)態(tài)規(guī)劃 可以先預(yù)處理出原數(shù)第i到j(luò)段的數(shù)值A(chǔ)i,j是多少，這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。 Fi，j表示把這個(gè)數(shù)前i位分成j段得到的最大乘積。 Fi,j=Fk,j-1*Ak+1,i, 1ki=n, j=m 時(shí)間復(fù)雜度為Omn2 由于有10000組數(shù)據(jù)，因此估計(jì)時(shí)間復(fù)雜度為10000*203=8*107 至于說(shuō)輸出，記錄轉(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;記錄決策點(diǎn) end; writeln(fl,m); print(l,m); writeln; end; close(input); close(output);end.2022-6-1310石子合并Description在一個(gè)圓形操場(chǎng)的四周擺放N堆石子(N100)，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并

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

6、312 示例：如果石子對(duì)數(shù)為 4 4 5 92022-6-1313 貪心法 N=5 石子數(shù)分別為3 4 6 5 4 2。 用貪心法的合并過(guò)程如下： 第一次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 顯然，貪心法是錯(cuò)誤的。2022-6-1314 分析 假設(shè)只有2堆石子，顯然只有1種合

7、并方案 如果有3堆石子，則有2種合并方案，(1,2),3)和(1,(2,3) 如果有k堆石子呢？ 不管怎么合并，總之最后總會(huì)歸結(jié)為2堆，如果我們把最后兩堆分開(kāi)，左邊和右邊無(wú)論怎么合并，都必須滿(mǎn)足最優(yōu)合并方案，整個(gè)問(wèn)題才能得到最優(yōu)解。如下圖：2022-6-1315 動(dòng)態(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 時(shí)間復(fù)雜度為O(n3)2022-6-1316 優(yōu)化 由于石子堆是一個(gè)圈，因此我們可以枚舉分開(kāi)的位置，首

8、先將這個(gè)圈轉(zhuǎn)化為鏈，因此總的時(shí)間復(fù)雜度為O(n4)。 這樣顯然很高，其實(shí)我們可以將這條鏈延長(zhǎng)2倍，擴(kuò)展成2n-1堆，其中第1堆與n+1堆完全相同，第i堆與n+i堆完全相同，這樣我們只要對(duì)這2n堆動(dòng)態(tài)規(guī)劃后，枚舉f(1,n),f(2,n+1),f(n,2n-1)取最優(yōu)值即可即可。 時(shí)間復(fù)雜度為O(8n3),如下圖：2022-6-1317 猜想 合并第i堆到第j堆石子的最優(yōu)斷開(kāi)位置si,j要么等于i+1，要么等于j-1，也就是說(shuō)最優(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時(shí)間復(fù)雜度為O(n2)2022-6-1320能量項(xiàng)鏈【問(wèn)題描述】在 Mars 星球上，每個(gè) Mars 人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有 N 顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤(pán)（吸盤(pán)是 Mars 人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤(pán)吸收的能量。如果前一顆能量珠的頭標(biāo)記為 m ，尾標(biāo)記為 r ，后一

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

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

12、到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針?lè)较虼_定其他珠子的順序?！据敵鑫募?輸出文件 energy.out 只有一行，是一個(gè)正整數(shù) E （ E 2.1*10 9 ），為一個(gè)最優(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)。 我們用記號(hào) 表示兩顆珠子的聚合操作，釋放總能量： (4 1) 2) 3）=10*2*3+10*3*5+10*5*10=7102022-6-1323 動(dòng)態(tài)規(guī)劃 該題與石子合并完

13、全類(lèi)似。 設(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 至于圈的處理，與石子合并方法完全相同，時(shí)間復(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個(gè)頂點(diǎn)（從1到N編號(hào)）的凸多邊形

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

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

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

18、1數(shù)據(jù)范圍：對(duì)于所有數(shù)據(jù),0nD2,只要證明d(1,3) +d(2,4)d(1,2)+d(3,4)連接兩邊，見(jiàn)圖3，由三角形的三邊關(guān)系定理即可證明。2022-6-1334 結(jié)論：青蛙在1號(hào)結(jié)點(diǎn)只能跳到2號(hào)結(jié)點(diǎn)或者n號(hào)結(jié)點(diǎn)。 如果青蛙跳到了2號(hào)結(jié)點(diǎn)，則問(wèn)題轉(zhuǎn)化為：從2出發(fā)，遍歷2.n一次僅一次的最短距離。 如果青蛙跳到了n號(hào)結(jié)點(diǎn)，則問(wèn)題轉(zhuǎn)化為：從n出發(fā)，遍歷2.n一次僅一次的最短距離。 這實(shí)際上是遞歸的思維，把問(wèn)題轉(zhuǎn)化為了本質(zhì)相同但規(guī)模更小的子問(wèn)題,如下圖。2022-6-1335 動(dòng)態(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)，總的時(shí)間復(fù)雜度為O(n2)。2022-6-1336 動(dòng)態(tài)規(guī)劃(2) F(i,j,0)表示還有ij號(hào)點(diǎn)沒(méi)訪問(wèn),且青蛙停在i的最小值 F(i,j,1)表示還有ij號(hào)點(diǎn)沒(méi)訪問(wèn),且青蛙停在j的最小值 狀態(tài)總數(shù)為n2，狀態(tài)轉(zhuǎn)移的復(fù)雜度為O(1)，總的時(shí)間復(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棋盤(pán)分割 將一個(gè)*的棋盤(pán)進(jìn)行如下分割：將原棋盤(pán)割下一塊矩形棋盤(pán)并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤(pán)共有n塊矩形棋盤(pán)。(每次切割都只能沿著棋盤(pán)格子的邊進(jìn)行) 原棋盤(pán)上每一格有一個(gè)分值，一塊矩形棋盤(pán)的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤(pán)按上述規(guī)則分割成n塊矩形棋盤(pán)，并使各矩形棋盤(pán)總分的均方差最小。均方差2022-6-1339 xi為第i塊矩形棋盤(pán)的總分。 請(qǐng)編程對(duì)給出的棋盤(pán)及n，求出O的最小值2022-6-1340Input 第1行為一個(gè)整數(shù)n(1 n 15)。 第2行至第9行