- #include<stdio.h>
- int A[50025],ret,N,T;
- void combine(int k)
- {
- int tmp=A[k]+A[k-1],j;
- ret+=tmp;
- for (int i=k;i<T-1;i++) A[i]=A[i+1];
- T--;
- for (j=k-1;j>0 && A[j-1]<tmp;j--) A[j]=A[j-1];
- A[j]=tmp;
- while (j>=2 && A[j]>=A[j-2])
- {
- int d=T-j;
- combine(j-1);
- j=T-d;
- }
- }
- int main()
- {
- while (scanf("%d",&N)!=EOF && N!=0)
- {
- for (int i=0;i<N;i++) scanf("%d",&A[i]);
- T=1;
- ret=0;
- for (int i=1;i<N;i++)
- {
- A[T++]=A[i];
- while (T>=3 && A[T-3]<=A[T-1]) combine(T-2);
- }
- while (T>1) combine(T-1);
- printf("%d\\n",ret);
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/251120137471.html
来源: http://www.codesnippet.cn/detail/251120137471.html