對于一列的石子歸并問題，除了樸素的O(n^3)的dp做法及其O(n^2)優化，還有GarsiaWachs算法。

算法流程是，找一個最小的k，使得a[k-1]<=a[k+1]，將a[k-1]和a[k]合并；從當前位置向前找到一個最大的i，使得a[i]>a[k-1]+a[k]，并將新合并的一堆移到i的后面；重復操作n-1次，直至只剩下1堆，答案就是每次合并結果累加起來。

1 #include <cstdio> 2 3 const int maxn = 105, inf = 0x3f3f3f3f; 4 5 struct Node { 6 int num, pre, next; 7 } a[maxn]; 8 9 inline void del(int x) { 10 int pp = a[a[x].pre].pre, nn = a[x].next; 11 a[pp].next = nn, a[nn].pre = pp; 12 } 13 14 inline void insert(int x, int y) { 15 a[x].pre = y, a[x].next = a[y].next; 16 a[a[y].next].pre = x, a[y].next = x; 17 } 18 19 int main() { 20 int n, ans = 0; 21 scanf("%d", &n); 22 a[0].num = a[n + 1].num = inf; 23 a[0].next = 1, a[n + 1].pre = n; 24 for (int i = 1; i <= n; ++i) { 25 scanf("%d", &a[i].num); 26 a[i].pre = i - 1, a[i].next = i + 1; 27 } 28 for (int t = 1; t <= n - 1; ++t) { 29 int x, y, sum; 30 for (int i = a[0].next; ; i = a[i].next) 31 if (a[a[i].pre].num <= a[a[i].next].num) { 32 x = i; 33 break; 34 } 35 sum = a[a[x].pre].num + a[x].num; 36 for (int i = a[a[x].pre].pre; ; i = a[i].pre) 37 if (a[i].num > sum) { 38 y = i; 39 break; 40 } 41 del(x); 42 a[x].num = sum; 43 printf("%d ttt\n", sum); 44 insert(x, y); 45 ans += sum; 46 } 47 printf("%d", ans); 48 return 0; 49 } Code Example

?

轉載于:https://www.cnblogs.com/Mr94Kevin/p/10926709.html

總結

以上是生活随笔為你收集整理的GarsiaWachs算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。