本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-10 19:07:20

题目传送门

思路

一道明显的贪心题。

我们不难发现，如果 $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;
}