对于一列的石子归并问题，除了朴素的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 
      
        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 }