洛谷p4393（BOI2007）Sequence 序列问题

发现以后发题目只需要截图就可以了hhh。

感觉这种题好难想啊。看看数据范围，复杂度应该是 $O\left(n\right)$O(n)，这就要我们舍弃脑中各种奇奇怪怪的想法了（当然有大佬可以用强大的数据结构+卡常等特技）。 $O\left(n\right)$O(n)，我们读入就已经 $O\left(n\right)$O(n)了，这就要求我们单独考虑每一个数对答案的贡献了。

我们来看某一个数 $a$a 的一边，如果左边那个数 $b$b 比他小，那么 $a$a 一定会被算入总贡献。
为什么呢？
①：假设 $a$a 左边的数都比它小，那么 $a$a 肯定会被合并。
②：假设 $a$a 左边有比他更大的数 $c$c ，为了得到最小代价， $a$a 和 $c$c 中间的数合并完肯定会向 $a$a合并。
于是 $a$a 肯定会被算入贡献一次。右边同理。

下面是代码

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define LL long long
int a[N];
LL ans;
int main(){
	int i, j, n, m;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(i = 1; i < n; i++) ans += max(a[i], a[i+1]);
	printf("%lld", ans);
	return 0;
}