CF 1795E Explosions?

标签: cf

有一个长度为 的数组 ,有如下两个操作:

  1. 任选一个 ,令 ,代价为
  2. 任选一个 ,令 ,代价为 。 如果操作 2 使得 了,那么就会接着对相邻的两个 进行 的操作 2,如此递归下去。

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

由于要一口气使所有 变成 0,则操作 2 之前必须用操作 1 把 数组变成单峰的,即存在一个 使得 严格单调递增, 严格单调递减。令 表示 单调递增的代价, 表示 单调递减的代价,则答案就是

好求, 求法一致,所以只用考虑如何求

容易想到单调栈,我们用一个二元组 来表示一个最高高度为 、宽度为 、相邻两数高差为 的阶梯。枚举 ,如果栈顶的 大于 ,则不单调,需要累加答案,并弹出栈顶,并使

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;
}