BZOJ-1345: [Baltic2007]序列问题Sequence

[文章目录]

Description

合并n-1次,每次将相邻的元素a,b合并,代价为max(a,b),合成后的元素为max(a,b)。求最小代价

贪心。考虑每一个元素,只能和两边与他最近且比他大的元素合并。那么维护一个单调递减的栈。每次加,如果不符合单调性弹出栈顶。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int z[1001000],n,top;
long long ans;
int read()
{
    int re=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
int main()
{
    int x,i;
    scanf("%d",&n);
    z[0]=0x7fffffff;
    for(i=1;i<=n;i++)
    {
        x=read();
        while(top>0&&x>=z[top])
            ans+=min(x,z[--top]);
        z[++top]=x;
    }
    for(int i=1;i<top;i++) ans+=z[i];
    printf("%lld\n",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注