这道题我是看的 DeepinC 的题解， 思路和大多数人不一样, 但是他写的不是很明白， 我来详细地描述一下
读入后扫一遍， 对于每一个平底坑， 预处理出来， 然后不断维护每一个坑的填一单位高度的代价 和代价增长率， 如果填坑更优， 那么就填。
注意， 因为代价增长是一个二次函数， 所以可以直接用公式(-dfrac {b} {2a})计算即可。
其他细节可以看代码
#include <bits/stdc++.h>
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })
char buf[1 << 20], *p1, *p2;
using namespace std;
int n, l[2000005], r[2000005], tot, rb[1000005], lb[1000005], c;
long long h[1000005], a[2000005], w[2000005], ans;
int main() {
freopen("construct.in", "r", stdin), freopen("construct.out", "w", stdout);
n = read(), c = read();
for (register int i = 1; i <= n; i++) h[i] = read();
for (register int i = 2; i <= n; i++) ans += abs(h[i] - h[i - 1]) * c; // 先计算一遍 ans
h[0] = h[n + 1] = INT_MAX;
for (register int i = 1, j; (j = i) <= n; i = j + 1) {
while (h[j + 1] == h[i]) j++; // 高度相同时， 不断扩展
if (h[i - 1] > h[i] && h[i] < h[j + 1]) {
l[++tot] = i; // 左端点
r[tot] = j; // 右端点
w[tot] = j - i + 1; // 当前高度下， 每建一单位高度所需代价
a[tot] = w[tot] * 2;// 高度每增加1， w[i] 所增加的值, 详细解释在第 43 行
}
}
for (register int i = 1; i <= tot; i++) {
// e 为增长一高度 不美观度减少的值， t为增加的高度
long long e = 0, t;
if (l[i] != 1) e += c;
if (r[i] != n) e += c;
// 如果增长一高度， 减少的不美观度少于代价， 处理下一个坑
if (e < w[i]) continue;
// 计算增加的高度， -(2 * a / b) 和 深度 取最小值
t = min((e - w[i]) / a[i] + 1, min(h[r[i] + 1], h[l[i] - 1]) - h[l[i]]);
h[l[i]] += t;
if (l[i] != r[i]) h[r[i]] += t;
// e * t 为减少的不美观值
ans -= e * t;
// 这里是一个等差数列求和公式， 首项为 w[i], 公差为 a[i], 共 t - 1 项
// w[i] 不同高度下， 增加一高度的代价， w[i] 求和即为增加 t 的代价
ans += (w[i] + (w[i] + (t - 1) * a[i])) * t / 2;
// 更新 w[i]
w[i] += a[i] * t;
// 高度增加后向左扩展
while (h[l[i]] == h[l[i] - 1] && !rb[l[i] - 1]) {
// 因为增加了一个之前没有增加过高度的点， 所以 w[i]++ (0 -> 1), 而 a[i] += 2
// 代价增长如下：
// 0 -> 1 -> 4 -> 9 -> 16 -> 25
// 则 w[i] 增长如下
// 1 -> 3 -> 5 -> 7 -> 9
// 则 a[i] 为
// 2 -> 2 -> 2 -> 2
// 所以每增加一个新点， a[i] += 2
l[i]--, w[i]++, a[i] += 2;
}
// 扩展到另一个坑， 合并
if (h[l[i]] == h[l[i] - 1])
w[i] += w[rb[l[i] - 1]], a[i] += a[rb[l[i] - 1]], l[i] = l[rb[l[i] - 1]];
// 向右同理
while (h[r[i]] == h[r[i] + 1] && !lb[r[i] + 1])
r[i]++, w[i]++, a[i] += 2;
if (h[r[i]] == h[r[i] + 1])
w[i] += w[lb[r[i] + 1]], a[i] += a[lb[r[i] + 1]], r[i] = r[lb[r[i] + 1]];
lb[l[i]] = rb[r[i]] = i; // 打上标记
// 如果 还能再增长， 就再计算一遍
i -= h[l[i] - 1] > h[l[i]] && h[r[i]] < h[r[i] + 1];
}
printf("%lld
", ans);
}