题解：CF442C Artem and Array

· · 题解

题目传送门

思路

一道明显的贪心题。

我们不难发现，如果 a_i \le a_{i-1} 并且 a_i \le a_{i+1}，那么删去 a_i 是最优的。

若删去 a_i，则我们得到的分值为 \min( a_{i-1}, a_{i+1} )，比 a_i 大。若不删去 a_i，则得到的分值最大为 a_i。说明在 a_i \le a_{i-1} 并且 a_i \le a_{i+1} 的情况下，删去 a_i 是最优的。

显然，剩下的序列分为三种情况：单调上升，单调下降或者是倒 V 型。

不难发现，无论如何删，序列的最大值和次大值的分数不可能取到。

若能取到最大值的分数，则必定有两个数比最大值大，不符实际。次大值同理。

所以，我们将答案还要加上 \sum\limits_{i = 1}^{n-2} a_i。（a 序列为删完的序列）

我们可以用栈来实现。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
#define int long long
const int N=5e5+55;
int a[N],vis[N];
int tot,res;
stack<int> st;
signed main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        int d;
        cin>>d;
        while(st.size()>=2){
            int x=st.top();//栈顶
            st.pop();
            int y=st.top();//栈的第二个
            if(x<=y&&x<=d){//这里是<=而不是<!!!!
                res+=min(y,d);
            }
            else{
                st.push(x);
                break;
            }
        }
        st.push(d);
    }
    while(!st.empty()){
        tot++;
        a[tot]=st.top();
        st.pop();
    }
    sort(a+1,a+tot+1);
    for(int i=1;i<=tot-2;i++) res+=a[i];
    cout<<res<<endl;
    return 0;
}