[文章目录]
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;
}