「CF442C」 Artem and Array

\(Solution\)

观察发现如果一个数两边都比他大，删掉他可以保证最优，这个应该是显然的。这个东西用单调栈维护一下，最后剩下的就是个单调递减或单调递增的数列，从小到大排个序取前面\(n-2\)个,\(n\)为数列长度

\(Code\)

#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
const int N=5e5+10;
stack<int> s;
int a[N];
main(){
    int n=read(),ans=0,x,y,tot=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        while(s.size()>=2){
            x=s.top(),s.pop(),y=s.top();
            if(y>=x&&x<=a[i]) ans+=min(a[i],y);
            else {s.push(x);break;}
        }
        s.push(a[i]);
    }
    while(!s.empty())
        a[++tot]=s.top(),s.pop();
    sort(a+1,a+1+tot);
    for(int i=1;i<tot-1;i++)
        ans+=a[i];
    printf("%lld",ans);
    return 0;
}