原題鏈接

描述????有N堆石子排成一排，每堆石子有一定的數(shù)量?，F(xiàn)要將N堆石子并成為一堆。合并的過程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費(fèi)的代價(jià)為這兩堆石子的和，經(jīng)過N-1次合并后成為一堆。求出總的代價(jià)最小值。

輸入

有多組測(cè)試數(shù)據(jù)，輸入到文件結(jié)束。
每組測(cè)試數(shù)據(jù)第一行有一個(gè)整數(shù)n，表示有n堆石子。
接下來的一行有n（0< n <200）個(gè)數(shù)，分別表示這n堆石子的數(shù)目，用空格隔開

輸出

輸出總代價(jià)的最小值，占單獨(dú)的一行

樣例輸入

3 1 2 3 7 13 7 8 16 21 4 18

樣例輸出

9 239

對(duì)于石子合并問題，有一個(gè)最好的算法，那就是GarsiaWachs算法。時(shí)間復(fù)雜度為O(n^2)。

它的步驟如下：

設(shè)序列是stone[]，從左往右，找一個(gè)滿足stone[k-1] <=?stone[k+1]的k，找到后合并stone[k]和stone[k-1]，再從當(dāng)前位置開始向左找最大的j，使其滿足stone[j] >?stone[k]+stone[k-1]，插到j(luò)的后面就行。一直重復(fù)，直到只剩下一堆石子就可以了。在這個(gè)過程中，可以假設(shè)stone[-1]和stone[n]是正無窮的。

?

舉個(gè)例子： 186 64 35 32 103 因?yàn)?5<103，所以最小的k是3，我們先把35和32刪除，得到他們的和67，并向前尋找一個(gè)第一個(gè)超過67的數(shù)，把67插入到他后面，得到：186 67 64 103,現(xiàn)在由5個(gè)數(shù)變?yōu)?個(gè)數(shù)了，繼續(xù)：186 131 103，現(xiàn)在k=2（別忘了，設(shè)A[-1]和A[n]等于正無窮大）234 186，最后得到420。最后的答案呢？就是各次合并的重量之和，即420+234+131+67=852。 ? 基本思想是通過樹的最優(yōu)性得到一個(gè)節(jié)點(diǎn)間深度的約束，之后證明操作一次之后的解可以和原來的解一一對(duì)應(yīng)，并保證節(jié)點(diǎn)移動(dòng)之后他所在的深度不會(huì)改變。具體實(shí)現(xiàn)這個(gè)算法需要一點(diǎn)技巧，精髓在于不停快速尋找最小的k，即維護(hù)一個(gè)“2-遞減序列”樸素的實(shí)現(xiàn)的時(shí)間復(fù)雜度是O(n*n)，但可以用一個(gè)平衡樹來優(yōu)化，使得最終復(fù)雜度為O(nlogn)。

代碼如下：

#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N = 50005; int stone[N]; int n,t,ans; void combine(int k) { int tmp = stone[k] + stone[k-1]; ans += tmp; for(int i=k;i<t-1;i++) stone[i] = stone[i+1]; t--; int j = 0; for(j=k-1;j>0 && stone[j-1] < tmp;j--) stone[j] = stone[j-1]; stone[j] = tmp; while(j >= 2 && stone[j] >= stone[j-2]) { int d = t - j; combine(j-1); j = t - d; } } int main() { while(scanf("%d",&n)!=EOF) { if(n == 0) break; for(int i=0;i<n;i++) scanf("%d",stone+i); t = 1; ans = 0; for(int i=1;i<n;i++) { stone[t++] = stone[i]; while(t >= 3 && stone[t-3] <= stone[t-1]) combine(t-2); } while(t > 1) combine(t-1); printf("%d\n",ans); } return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/chen9510/p/5781884.html

總結(jié)

以上是生活随笔為你收集整理的NYOJ 737---石子归并（GarsiaWachs算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。