C++14(g++5.4) 解法, 执行用时: 117ms, 内存消耗: 580K, 提交时间: 2020-09-21 16:56:32

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 50005;
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()
{
    while(1)
    {
        scanf("%d", &n);
        if(!n)
            break;
	    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);
        memset(stone,0,sizeof stone);
    }
	
	return 0;

}

C++(g++ 7.5.0) 解法, 执行用时: 116ms, 内存消耗: 492K, 提交时间: 2022-08-12 16:35:56

#include<cstdio>
using namespace std;
const int N=5e4+5;
int n,t,ans,stone[N];
void combine(int k)
{
    int tmp=stone[k]+stone[k-1]; 
    ans+=tmp;
    for(int i=k;i<t-1;i++)
    stone[i]=stone[i+1]; 
    t--;
    int j=0;
    for(j=k-1;j>0&&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()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
        for(int i=0;i<n;i++)
        scanf("%d",stone+i);
        t=1;
        ans=0;
        for(int i=1;i<n;i++)
        {
            stone[t++]=stone[i];
            while(t>=3&&stone[t-3]<=stone[t-1])
            combine(t-2);
        }
        while(t>1)combine(t-1);
        printf("%d\n",ans);
    }
    return 0;
}

C++ 解法, 执行用时: 120ms, 内存消耗: 524K, 提交时间: 2022-02-02 14:48:52

#include<bits/stdc++.h>
using namespace std;
int n,a[50001],t,p,ans;
void wk(int x){
	int k=a[x]+a[x-1];
	ans+=k;
	for(int i=x;i<t-1;i++)a[i]=a[i+1];
	t--;
	for(p=x-1;p&&a[p-1]<k;p--)a[p]=a[p-1];
	a[p]=k;
	while(p>=2&&a[p]>=a[p-2]){int d=t-p;wk(p-1);p=t-d;}
}
int main(){
	while(cin>>n&&n){
		for(int i=0;i<n;i++)cin>>a[i];
		t=1,ans=0;
		for(int i=1;i<n;i++){a[t++]=a[i];while(t>=3&&a[t-3]<=a[t-1])wk(t-2);}
		while(t>1)wk(t-1);
		cout<<ans<<"\n";
	}
	return 0;
}