[bzoj1345]序列问题

记每一个数向比他大的数合并时的代价为这个数字的代价，显然除了最大值以外，每一个数都有一个代价，那么这个代价和就是最终答案
考虑最小化这个代价和，也就是让每一个数的代价最小，显然这个代价不会小于向左和右第一个比他大的数中较小的数，然后这样的方案也很好构造，这个东西用单调栈来处理即可

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n,a[N],lmx[N],rmx[N],s[N];
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    memset(lmx,0x3f,sizeof(lmx));
    memset(rmx,0x3f,sizeof(rmx));
    for(int i=1;i<=n;i++){
        while ((s[0])&&(s[s[0]]<a[i]))s[0]--;
        if (s[0])lmx[i]=s[s[0]];
        s[++s[0]]=a[i];
    }
    s[0]=0;
    for(int i=n;i;i--){
        while ((s[0])&&(s[s[0]]<a[i]))s[0]--;
        if (s[0])rmx[i]=s[s[0]];
        s[++s[0]]=a[i];
    }
    for(int i=1;i<=n;i++)ans+=min(lmx[i],rmx[i]);
    printf("%lld",ans-0x3f3f3f3f);
}