P14324 题解

Gapple · 2026-11-11 16:32:44 · 题解

我们先考虑：如果同时知道 h_{i - 1} 和 h_{i + 1}，那么 h_i 应该怎么变？发现只有 h_i < \min(h_{i - 1}, h_{i + 1}) 时，给 h_i 做操作才不劣。所以最终的操作序列一定形如下图：

也就是说，最终在 h 中会有一些位置没有动过，它们之间的位置分别会被抬高到同一高度。

于是我们 DP：设 f(i) 表示只考虑前 i 个数，且第 i 个没有动过时的答案。

如何转移？枚举上一个没有动过的位置 j，考虑计算最优的高度 x，使得把 (j, i) 之间的 h 都抬升到 x 后，这一部分的代价最低。发现代价就是

这是二次函数求最小值。注意特殊处理 j = 0 和 i = n + 1。

但是问题在于：转移点还是太多了。发现为了让 F 有定义，必须有 \max \limits_{j < k < i} (h_k) < \min(h_i, h_j)，而这样的 j 可以用单调栈维护。这样转移点总数就是 O(n) 的。

:::info[Code]

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;
using i64 = long long;

constexpr i64 INF = 0x3f3f3f3f3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, c;
    cin >> n >> c;

    vector<int> h(n);
    for (int& x : h)
        cin >> x;

    vector<int> pre_max(n), suf_max(n);
    vector<i64> pre_sum(n), pre_sum2(n);
    for (int i = 0; i < n; ++i) {
        pre_max[i] = i > 0 ? max(pre_max[i - 1], h[i]) : h[i];
        pre_sum[i] = (i > 0 ? pre_sum[i - 1] : 0) + h[i];
        pre_sum2[i] = (i > 0 ? pre_sum2[i - 1] : 0) + h[i] * i64(h[i]);
    }
    for (int i = n - 1; i >= 0; --i)
        suf_max[i] = i == n - 1 ? h[i] : max(suf_max[i + 1], h[i]);

    auto sum_h = [&](int l, int r) { return pre_sum[r] - (l > 0 ? pre_sum[l - 1] : 0); };
    auto sum2_h = [&](int l, int r) { return pre_sum2[r] - (l > 0 ? pre_sum2[l - 1] : 0); };

    auto cost_seg = [&](int l, int r, int mx) {
        if (l + 1 == r)
            return c * llabs(h[r] - h[l]);

        int lo = mx, hi = min(h[l], h[r]);
        if (lo > hi)
            return INF;

        // f(x) = \sum_{l < i < r} (x - h[i])^2 + c * (h[l] + h[r] - 2x), x \in [\max_{l < i < r} h[i], \min(h[l], h[r])]
        auto cost = [&](int x) { return x < lo || x > hi ? INF : i64(r - l - 1) * x * x - 2 * x * sum_h(l + 1, r - 1) + sum2_h(l + 1, r - 1) + c * i64(h[l] + h[r] - 2 * x); };
        int x_min = clamp<i64>((sum_h(l + 1, r - 1) + c) / (r - l - 1), lo, hi);
        return min(cost(x_min), cost(x_min + 1));
    };

    auto cost_left = [&](int r, int mx) {
        if (r == 0)
            return 0LL;

        int lo = mx, hi = h[r];
        if (lo > hi)
            return INF;

        // f(x) = \sum_{0 <= i < r} (x - h[i])^2 + c * (h[r] - x), x \in [\max_{0 <= i < r} h[i], h[r]]
        auto cost = [&](int x) { return x < lo || x > hi ? INF : i64(r) * x * x - 2 * x * sum_h(0, r - 1) + sum2_h(0, r - 1) + c * i64(h[r] - x); };
        int x_min = clamp<i64>((2 * sum_h(0, r - 1) + c) / (2 * r), lo, hi);
        return min(cost(x_min), cost(x_min + 1));
    };

    auto cost_right = [&](int l, int mx) {
        if (l == n - 1)
            return 0LL;

        int lo = mx, hi = h[l];
        if (lo > hi)
            return INF;

        // f(x) = \sum_{l < i < n} (x - h[i])^2 + c * (h[l] - x), x \in [\max_{l < i < n} h[i], h[l]]
        auto cost = [&](int x) { return x < lo || x > hi ? INF : i64(n - l - 1) * x * x - 2 * x * sum_h(l + 1, n - 1) + sum2_h(l + 1, n - 1) + c * i64(h[l] - x); };
        int x_min = clamp<i64>((2 * sum_h(l + 1, n - 1) + c) / (2 * (n - l - 1)), lo, hi);
        return min(cost(x_min), cost(x_min + 1));
    };

    i64 ans = INF;
    vector<int> stk, mx(n);
    vector f(n, INF);
    for (int i = 0; i < n; ++i) {
        f[i] = cost_left(i, i == 0 ? -1 : pre_max[i - 1]);
        while (!stk.empty() && h[stk.back()] <= h[i]) {
            int j = stk.back();
            f[i] = min(f[i], f[j] + cost_seg(j, i, mx[i]));
            mx[i] = max({ mx[i], mx[j], h[j] });
            stk.pop_back();
        }
        if (!stk.empty()) {
            int j = stk.back();
            f[i] = min(f[i], f[j] + cost_seg(j, i, mx[i]));
        }
        stk.push_back(i);
        ans = min(ans, f[i] + cost_right(i, i == n - 1 ? -1 : suf_max[i + 1]));
    }

    cout << ans << '\n';
    return 0;
}

:::