石子合并最快算法

#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;

const int N = 50005;
const int INF = 0x7fffffff;
typedef long long LL;
int stone[N];
int n,t;
LL ans;

void combine(int k)
{
    LL tmp = (LL)stone[k] + (LL)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;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()
{
    //freopen("D:\\input.in","r",stdin);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",stone+i);///连续石子堆石子个数
        stone[0]=INF;
        stone[n+1]=INF-1;
        t = 3;
        ans = 0;
        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("%lld\n",ans);
    }
    return 0;
}