解题思路

当石子堆数达到$50000$堆时，传统动态规划所需的$int[50000][50000]$数组会导致空间和时间复杂度过高，此时 GarsiaWachs 算法成为更优选择。

该算法从第一个石堆开始找符合$stone[k-1]< (stone[k+1]$的石堆k，然后合并$k-1$与$k$堆，再向前找j堆石子，满足$stone[j] > (stone[k] + stone[k-1]$，插入到石堆$j$的后面，之后重新寻找符合条件的位置重复操作。

$GarsiaWachs$算法的核心想法在于：将石子视为三堆$k-1、k、k+1$，若$stone[k-1] < (stone[k+1]$，先合并$k-1$与k堆是合理的。合并后将新堆插入到$stone[j]$后面（其中$stone[j]$是第一个大于新堆重量的前趋堆），本质是将$stone[j+1]$与$stone[k-2]$视为整体$stone[m]$，形成$stone[j]$、$stone[m]$、新堆的结构。由于新堆重量小于$stone[j]$，后续会优先合并$stone[m]$与新堆，通过这种局部最优决策的迭代，最终可得到全局最优的归并结果。

标程

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAXN = 55555;
const int INF = 1 << 30;

struct ARC {
    int last;
    int next;
    int data;

    void init() {
        next = last = 0;
        data = INF;
    }
};

ARC arc[MAXN];

void in(int& cnt) {
    arc[cnt].next = cnt + 1;
    arc[cnt + 1].last = cnt;
    scanf("%d", &arc[++cnt].data);
}

void del(int u) {
    arc[arc[u].last].next = arc[u].next;
    arc[arc[arc[u].last].next].last = arc[u].last;
}

void reinsert(int x, int u) {
    for (int i = arc[u].last; ; i = arc[i].last) {
        if (arc[i].data > x) {
            arc[u].last = i;
            arc[u].data = x;
            arc[u].next = arc[i].next;
            arc[arc[u].next].last = u;
            arc[i].next = u;
            return;
        }
    }
}

void work(int n) {
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i <= n + 1; i++) {
        arc[i].init();
    }
    for (int i = 1; i <= n; i++) {
        in(cnt);
    }
    for (int i = 1; i < n; i++) {
        for (int j = arc[0].next; j; j = arc[j].next) {
            int l = arc[j].last;
            int r = arc[j].next;
            if (arc[l].data <= arc[r].data) {
                del(l);
                del(j);
                int weight = arc[l].data + arc[j].data;
                ans += weight;
                reinsert(weight, j);
                break;
            }
        }
    }
    printf("%d\n", ans);
    return;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF && n) {
        work(n);
    }
    return 0;
}