Artem and Array

Codeforces Round #253 (Div. 1) C:http://codeforces.com/problemset/problem/442/C

题意:给你一个序列，然后你每次可以删除一个数，然后得到一个价值，这个价值是这个数左右相邻数的小的那一个。问你最多能取得多少价值。

题解：首先可以证明，如果两个大的数之间夹着一个小的数，那么这个小的数可以直接删除，这样贪心是正确的。最后得到的序列只可能是递增或者递减或者先递增后递减。对于前面两种，可以知道，从倒数第二大的数开始往小的数删除，这样贪心是正确的。对于，第三种来说，排完序后发现，也可以行倒数第二大的开始。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5*1e5+4;
long long a[N],temp,ans;
int n,top;
int main(){
   while(~scanf("%d",&n)){
       ans=top=0;
      for(int i=1;i<=n;i++){
          scanf("%I64d",&temp);
          while(top>1&&a[top]<=temp&&a[top]<=a[top-1]){
              ans+=min(a[top-1],temp);
              top--;
          }
          a[++top]=temp;
      }
      sort(a+1,a+top+1);
      for(int i=1;i<=top-2;i++)
        ans+=a[i];
      printf("%I64d
",ans);
   }
}