C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 536K, 提交时间: 2020-09-21 16:48:58

/*

在一个操场上摆放着一排 N 堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 
试设计一个算法，计算出将 N 堆石子合并成一堆的最小得分。  
输入描述:
第一行是一个数N。
以下N行每行一个数A，表示石子数目。
输出描述:
共一个数，即N堆石子合并成一堆的最小得分。

 */
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 40005;
int stone[maxn], n, ans, t;

void combine(int k)
{
	int tmp = stone[k-1]+stone[k];
	ans += tmp;
	--t;
	for(int i = k; i < t; ++i) stone[i] = stone[i+1];
	int j;
	for(j = k-1; stone[j-1] < tmp; --j)
		stone[j] = stone[j-1];
	stone[j] = tmp;
	while(j >= 2 && stone[j] >= stone[j-2])
	{
		int d = t-j;
		combine(j-1);
		j = t-d;
	}
}

int main()
{
	scanf("%d", &n);
	stone[0] = inf; stone[n+1] = inf-1;
	for(int i = 1; i <= n; ++i)
		scanf("%d", &stone[i]);
	ans = 0; t = 3;
	for(int i = 3; i <= n+1; ++i)
	{
		stone[t++] = stone[i];
		while(stone[t-3] <= stone[t-1])
			combine(t-2);
	}
	while(t > 3) combine(t-1);
	printf("%d\n", ans);
	return 0;

}

C++(clang++ 11.0.1) 解法, 执行用时: 580ms, 内存消耗: 1036K, 提交时间: 2022-12-18 16:40:36

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll n,ans;
vector<ll>vec;
void work()
{
	while (vec.size() > 1)
	{
		ll idx = vec.size() - 2;
		for (ll i = 0; i < vec.size() - 2; i++)
		{
			if (vec[i] <= vec[i + 2])
			{
				idx = i;
				break;
			}
		}
		ll tmp = vec[idx] + vec[idx + 1];
		vec.erase(vec.begin() + idx);//删除idx
		vec.erase(vec.begin() + idx);//删除idx+1，但此时已经到idx了
		ll k = -1;
		for (ll i = idx - 1; i >= 0; i--)
		{
			if (vec[i] > tmp)
			{
				k = i;
				break;
			}
		}
		vec.insert(vec.begin()+(k+1), tmp);
		ans += tmp;
	}
}
int main()
{
	cin >> n;
	for (ll i = 1; i <= n; i++)
	{
		ll now; cin >> now;
		vec.push_back(now);
	}
	work();
	cout << ans;
	return 0;
}