题意：
给你一个序列，长度为n。你需要进行n - 1次操作，每次合并两个相邻的数，代价是max，合并后成为max，求最小代价。
n <= 1e6
解：
有个显然的做法是nlogn的，显然不行...
要搞个O(n)的算法，显然是贪心。
然而想不出来...
主要有两种思路。
①合并成一颗树。从根向下考虑。
根的贡献就是他的子节点数。
然后问题递归。
我们还可以证明有一种最优解，每个位置的数至多被合并2次。
那么就是一颗大根堆。
也可以说：若一个数的旁边比他小，那么一定会有一次合并过来，贡献为他自己。
所以做法就是：每个数的贡献是他两边比他小的个数。
②由于每次要合并小的，就开个单调栈，下面大。
每次出栈时合并，最后再合并栈中的数即可。
记得开long long
1 #include <cstdio> 2 #include <algorithm> 3 typedef long long LL; 4 const int N = 1000010; 5 6 int a[N]; 7 8 int main() { 9 int n; 10 scanf("%d", &n); 11 if(n == 1) { 12 scanf("%d", &a[1]); 13 printf("0"); 14 return 0; 15 } 16 if(n == 2) { 17 scanf("%d%d", &a[1], &a[2]); 18 printf("%d", std::max(a[1], a[2])); 19 return 0; 20 } 21 scanf("%d%d", &a[1], &a[2]); 22 LL ans = 0; 23 if(a[1] > a[2]) { 24 ans += a[1]; 25 } 26 for(int i = 3; i <= n; i++) { 27 scanf("%d", &a[i]); 28 if(a[i - 1] > a[i - 2]) { 29 ans += a[i - 1]; 30 } 31 if(a[i - 1] > a[i]) { 32 ans += a[i - 1]; 33 } 34 } 35 if(a[n] > a[n - 1]) { 36 ans += a[n]; 37 } 38 printf("%lld", ans); 39 return 0; 40 }