https://www.luogu.org/problem/P4393
题意
给你n个点的一个数列，每次可以合并两个相邻的数为他们的最大值，且代价为这两个数的最大值，求将整个序列合并为1个数的最小代价
n≤1e6
分析
个人做这题很玄.....
我们先考虑三个数a,b,c , 且序列的顺序为{a, b, c}的情况...可得
当 a < b < c时，在最优的情况下， 最大值c只有一次被计算在内(即只对最终的代价 的贡献是一个c）， 并且，b被算了一次。
当a < b, b > c时， 最大值b被计算了两次，而a和没有被计算在内
这样，多画几个图自己看看（虽然找规律（即找贪心的策略）花费的时间可能比较多...像我做这题的时候就是在纸上涂涂画画...）， 然后我们就可以得出贪心策略：
我们将每个点 i 与它左右两边相邻点i-1, i+1比较大小，并记录比a[i]小的相邻点的个数is[i]（0， 1 或2），那么a[i]对答案（即最终代价）的贡献就是a[i]*is[i].
证明： a[i]>a[i-1] && a[i]>a[i+1]时， 无论怎么合并 i 两边的数， 到后来， a[i]总被计算两次。
只有一个成立时(假设是a[i]>a[i+1]不成立）， a[i]总被计算一次，而a[i+1]的计算次数就 >= 1了，a[i] 一定是与a[i+1]合并的。
注意合并操作的实现和边界1， n的is值即可（其实我也就是试试，谁知道真过了emm....
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 1000000int n;
int a[MAX];
int is[MAX];int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d",&a[i]); for(int i = 2; i < n; i++) {if(a[i] >= a[i+1]) {is[i]++;if(a[i] == a[i+1]) is[i+1]--;}if(a[i] >= a[i-1]) is[i]++;}if(a[1] > a[2]) is[1] = 1;if(a[n] > a[n-1]) is[n] = 1;ll ans = 0;for(int i = 1; i <= n; i++) {ans += (ll)a[i]*is[i];}printf("%lld",ans);
}