Problem B. Pancake Pyramid
Brief Description
给定长度为 n 的序列 h[i]。
每次你可以选择一段连续子序列 [l, r]，你可以给其中某些项执行 +1 操作，使得操作后形成一个金字塔形状（先递增再递减）。
问遍历所有的子序列，总操作次数最少是多少。
Analysis
相同元素可能会带来重复计数，我们统一先认为相同的元素出现时，左边的更大。
考虑暴力做法。注意到我们这里 只有 +1 操作，所以可以直接贪心。
每次枚举区间，设:
– M[l][r] 表示 [l, r] 区间最大的数的位置。
– L[l][r] 表示把 [l, r] 这个区间处理成递增序列的最小代价。
– R[l][r] 表示把 [l, r] 这个区间处理成递减序列的最小代价。
那么我们枚举所有的区间，统计所有 L[l][m] + R[m][r] 就是答案，可以预处理这些数组，复杂度 O(n2)，可以过小数据。
考虑大数据，其实题目里已经疯狂暗示你了要用单调栈（stack）。。。
回忆 POJ 2559. Largest Rectangle in a Histogram。
我们发现之前是要处理出，以 h[i] 为最低点，左右两边分别可以延伸多远。
这里恰好是求，以 h[i] 为最高点，左右两边分别可以延伸多远，假设就是 Dl[i] 和 Dr[i]。
这样唯一不同的是，我们还需要一个累计代价数组 Sl[i] 和 Sr[i]，分别表示以 h[i] 为最高点，往左和往右累计的代价。
因为最后答案就是：
$$\Sigma_{i=1}^n Dl[i] * Sr[i] + Dr[i] * Sl[i]$$
我们可以在维护单调栈的过程中，顺路求 Sl 出 Sr。不放考察从左往右扫描求 Dl 的过程。
设当前扫描到位置 i，将要被弹出的栈顶元素为 sp，这个位置右边一直到 i 这个区间现在都至少需要是 h[sp] 的高度才符合要求。
记这个代价为小写的 sl，我们预处理部分和后可以 O(1) 的求出 sl。记新的栈顶元素的位置与刚才被我们弹出的栈顶元素的位置之间的距离为 sp – s.top()，
sl 需要被统计 sp – s.top() 次。最后加上这个区间本身的代价 Sl[sp]。
stack<int> s; s.push(0); REP_1(i, n) {
Sl[i] = 0;
while (h[i] > h[s.top()]) {
int sp = s.top(); s.pop();
Int sl = Int(h[sp]) * (i-sp-1) - (hh[i-1]-hh[sp]);
Sl[i] += sl * (sp - s.top()) + Sl[sp];
}
Dl[i] = i - s.top();
s.push(i);
}
