AW305 一个古老的石头游戏

题目地址

---

注意点：

• 开不下数组，只能用GarsiaWachs.

---

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=50010;
int a[MAXN],tot,ans;
void unions(int x){
    int tmp=a[x]+a[x-1];
    ans+=tmp;
    for(int i=x;i<tot;i++) a[i]=a[i+1];
    int j;
    for(j=x-1;a[j-1]<tmp && j>1;j--)
        a[j]=a[j-1];
    a[j]=tmp;
    tot--;
    for(int d=tot-j;j>2&&a[j-2]<=a[j];d=tot-j){
        unions(j-1);
        j=tot-d;
    }
}
int main() {
	int n;
    while(scanf("%d",&n)&&n){
        ans=tot=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            a[++tot]=a[i];
            while(tot>2 && a[tot-2]<=a[tot])unions(tot-1);
        }
        while (tot>1) unions(tot);
        printf("%d
",ans);
    }
    return 0;
}