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=*1e5+;

 long long a[N],temp,ans;

 int n,top;

 int main(){

    while(~scanf("%d",&n)){

        ans=top=;

       for(int i=;i<=n;i++){

           scanf("%I64d",&temp);

           while(top>&&a[top]<=temp&&a[top]<=a[top-]){

               ans+=min(a[top-],temp);

               top--;

           }

           a[++top]=temp;

       }

       sort(a+,a+top+);

       for(int i=;i<=top-;i++)

         ans+=a[i];

       printf("%I64d\n",ans);

    }

 }

巴特西

Artem and Array

最新文章

热门文章