CF 1795E Explosions?

標籤： cf

有一个长度为 $n$ 的数组 $h_i$，有如下两个操作：

1. 任选一个 $i$，令 $h_i \gets h_i - 1$，代价为 $1$。
2. 任选一个 $i, x$，令 $h_i \gets h_i - x$，代价为 $x$。 如果操作 2 使得 $h_i = 0$ 了，那么就会接着对相邻的两个 $h_{i-1}$ 和 $h_{i+1}$ 进行 $x = h_i - 1$ 的操作 2，如此递归下去。

只能使用一次操作 2，且操作 2 要能把所有非 0 的 $h$ 变成 0，问最小代价。

由于要一口气使所有 $h_i$ 变成 0，则操作 2 之前必须用操作 1 把 $h$ 数组变成单峰的，即存在一个 $i$ 使得 $h_0$ 到 $h_i$ 严格单调递增，$h_i$ 到 $h_{n-1}$ 严格单调递减。令 $pre_i$ 表示 $0$ 到 $i$ 单调递增的代价，$back_i$ 表示 $i$ 到 $n-1$ 单调递减的代价，则答案就是 $\min\{pre_i + back_i + h_i\}$。

$h_i$ 好求，$pre_i$ 和 $back_i$ 求法一致，所以只用考虑如何求 $pre_i$。

容易想到单调栈，我们用一个二元组 $(h, w)$ 来表示一个最高高度为 $h$、宽度为 $w$、相邻两数高差为 $1$ 的阶梯。枚举 $i$，如果栈顶的 $h_{top}$ 大于 $h_i - w_i$，则不单调，需要累加答案，并弹出栈顶，并使 $w_i \gets w_i + w_top$。

struct node_t
{
    int h, w;
    node_t() {}
    node_t(int h, int w) : h(h), w(std::min(h, w)) {}
    long long maxsize(int h)
    {
        return (long long)h * (h + 1) / 2;
    }
    long long size()
    {
        if (h <= w) return maxsize(h);
        return maxsize(h) - maxsize(h - w);
    }
};
 
void solve()
{
    int n;
    cin >> n;
    vector<int> h(n);
    for (auto &i : h) cin >> i;
 
    auto calc_pre = [](const std::vector<int> &h) -> std::vector<long long>
    {
        int n = h.size();
        std::vector<long long> res(n);
        std::stack<node_t> s;
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            node_t cur(h[i], 1);
            while (!s.empty() && cur.h - cur.w < s.top().h) {
                node_t tmp = s.top();
                s.pop();
                node_t new_cur = node_t(cur.h, cur.w + tmp.w);
                ans += cur.size() + tmp.size() - new_cur.size();
                cur = new_cur;
            }
            s.emplace(cur);
            res[i] = ans;
        }
        return res;
    };
    auto pre = calc_pre(h);
    std::ranges::reverse(h);
    auto back = calc_pre(h);
    std::ranges::reverse(h);
    std::ranges::reverse(back);
    auto ans = std::numeric_limits<long long>::max();
    for (int i = 0; i < n; i++) {
        ans = std::min(ans, pre[i] + back[i] + h[i]);
    }
    cout << ans << endl;
}