更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527165

大意

求最小值的石子合并，$n \le 40000$。

思路

利用 GarsiaWachs 算法。

在序列中找到第一个满足 $a_{i-1} \le a_{i+1}$ 的三元组 $(a_{i-1}, a_i, a_{i+1})$。

合并 $a_{i-1}$ 和 $a_i$，得分增加 $W = a_{i-1} + a_i$。

从当前位置向左寻找第一个大于 $W$ 的位置，将 $W$ 插入到其后面。

重复上述过程，直到只剩下一堆石子。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define int long long
int n;
int ans = 0;
vector<int> a;

void merge(int k){
	int tmp = a[k - 1] + a[k];
	ans += tmp;
	a.erase(a.begin() + k - 1);
	a.erase(a.begin() + k - 1);
	int pos = -1;
	for(int i = k - 2;i >= 0;i --){
		if(a[i] >= tmp){
			pos = i;
			break;
		}
	}
	a.insert(a.begin() + pos + 1, tmp);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++){
		int val; cin >> val;
		a.push_back(val);
	}
	while(a.size() > 1){
		int k = a.size() - 1;
		for(int i = 1;i < (int)a.size() - 1;i ++){
			if(a[i - 1] <= a[i + 1]){
				k = i;
				break;
			}
		}
		merge(k);
	}
	cout << ans << '\n';
	return 0;
}