GarsiaWachs算法

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

部分代码：

using namespace std;
#define maxn 50010
typedef long long ll;
ll st[maxn];
int n,t;
ll ans;
inline void combine(int x){
	ll tmp = st[x] + st[x - 1];
	ans += tmp;
	for(int i = x;i < t - 1;i++){
		st[i] = st[i + 1];
	}
	t--;
	int j = 0;
	for(j = x - 1;j > 0 && st[j - 1] < tmp;j--){
		st[j] = st[j - 1];
	}
	st[j] = tmp;
	while(j >= 2 && st[j] > st[j - 2]){
		int d = t - j;
		combine(j - 1);
		j = t - d;
	}
} 
int main() {
	//ios::sync_with_stdio(0); cin.tie(0);
	int n;scanf("%d",&n);
	for(int i = 0;i < n;i++)scanf("%lld",&st[i]);
	t = 1;ans = 0;
	for(int i = 1;i < n;i++){
		st[t++] = st[i];
		while(t >= 3 && st[t - 3] <= st[t - 1]){
			combine(t - 2);
		}	
	}
	while(t > 1)combine(t - 1);
	printf("%lld
",ans);
	return 0;
}