石子合并

http://www.51nod.com/Challenge/Problem.html#problemId=1023

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e4+1;
long long a[maxn], b[maxn], tot, ans;

void combine(int x) {
    long long i, d, temp;
     temp = b[x] + b[x+1];
    for(i = x+1; i <= tot-1; i++) {
        b[i] = b[i+1];
    }
     ans += temp, tot -= 1;
    for(i = x-1; i >= 1 && b[i] <= temp; i--) {
        b[i+1] = b[i];
    }
     b[i+1] = temp;
     while(i >= 2 && b[i-1] <= b[i+1])
     {
          d = tot-i;
          combine(i-1);
          i = tot-d;
     }
}

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