【洛谷P4393】Sequence

题目大意：给定一个长度为 N 的序列，每次可以合并相邻的两个元素，代价是两者中较大的值，合并之后的值也为两者较大的值，求合并 N-1 次后的最小代价是多少。

题解：

除了最大值以外，每个值均只会被合并一次，合并的代价一定是这个值左边最大值和右边最大值中较小的那一个。问题转化成了如何求解每个元素左边和右边第一个大于该元素的值，单调栈扫一遍即可。

注意：如果有相同的元素，如4 2 2 3，中间两个 2 在最后计算答案时会产生错误，避免的方式是计算每个元素右边的值取大于等于，左边取大于即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

const int inf=0x3f3f3f3f;

typedef long long LL;

int n,a[maxn],l[maxn],r[maxn],stk[maxn],top;

LL ans;

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	a[0]=a[n+1]=inf;

	for(int i=1;i<=n+1;i++){

		while(top&&a[stk[top]]<=a[i])r[stk[top--]]=i;

		stk[++top]=i;

	}

	top=0;

	for(int i=n;~i;i--){

		while(top&&a[stk[top]]<a[i])l[stk[top--]]=i;

		stk[++top]=i;

	}

	for(int i=1;i<=n;i++){

		if(l[i]<1&&r[i]>n)continue;

		if(l[i]>=1&&r[i]<=n)ans+=min(a[l[i]],a[r[i]]);

		else if(r[i]>n)ans+=a[l[i]];

		else if(l[i]<1)ans+=a[r[i]];

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

【洛谷P4393】Sequence

最新文章

热门文章