CF1795E Explosions? (单调栈）

传送门

题意：

有 n 个怪兽需要消灭，它们的生命值分别是 h [1],h [2]......h [n].

我们可以使用两种技能：

技能 1：选择任意一个怪兽，使其生命值降低 1 点，并且需要 1 点能量值.

技能 2：选择任意一个怪兽，使其生命值降低 x 点，需要花费 x 点能量值.

如果使用技能 2之后消灭了被选择的怪兽，那么会接着对其相邻的怪兽造成 h[ i ] - 1点伤害值. 注意：技能 2 只能使用一次！

问题：

消灭所有的怪兽最少需要花费多少能量值 ?

思路：

假设把第 i 个怪兽作为Explosion的目标，那么要求 h[1] -> h[ i ] 变成严格单调递增，h[ i ] -> h[ n ]变成严格单调递减.

我们称把 1~ i 的生命值修改为严格单调递增的代价为 L[ i ]，i 到 n 的生命值修改为严格单调递减的代价是 R[ i ].

那么答案就是 min {L[ i ] + R[ i ] + h[ i ] }，那么现在，问题变成了如果求出 L[ i ] 和 R[ i ].

我们只需要考虑如果求出 L[ i ]即可，因为R[ i ]可以用类似的方法求得.

考虑一个经典技术：单调栈.

做法：

单调栈：

从左到右扫一遍过去.

栈中维护一个二元组(hi,cnt)表示当前有一个怪兽血量为h[ i ]，在它左边有 cnt - 1个怪兽，它们的血量从左到右单调递增且差值为 1.

栈中 h[ i ]严格单调递增.

当扫描到 i 时，实时维护一个sum，表示当前的L[ i ]，如果h[ i ] > 栈顶的 h，则L[ i ] = sum，并将(hi,1)加入栈，否则，要把栈顶的(h,cnt)这cnt 个怪兽的血量全部减去 h - hi +1，才能满足条件，我们把原先的栈顶 pop.

重复这个过程，直到栈为空或者 hi > 栈顶的 h，最终，我们将(hi,cnt1)加入栈，这里的cnt1表示 1 + pop出来的cnt的和.

参考代码：

#include <bits/stdc++.h>using LL = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {int n;std::cin >> n;std::vector<int> h(n);for (int i = 0; i < n; i++) {std::cin >> h[i];}std::vector<LL> L(n);std::vector<LL> R(n);for (int rot = 0; rot < 2; rot++) {std::vector<std::pair<LL, LL>> st;LL sum{};for (int i = 0; i < n; i++) {LL cnt = 1;while (!st.empty() && h[i] - cnt < st.back().first) {LL diff = st.back().first - (h[i] - cnt);sum += diff * st.back().second;cnt += st.back().second;st.pop_back();}if (cnt - 1 > h[i]) {LL extra = cnt - 1 - h[i];sum -= extra * (extra + 1) >> 1;cnt = h[i];}L[i] = sum;st.emplace_back(h[i], cnt);}std::reverse(L.begin(), L.end());std::reverse(R.begin(), R.end());std::reverse(h.begin(), h.end());std::swap(L, R);}LL ans = (LL)1e18;for (int i = 0; i < n; i++) {ans = std::min(ans, L[i] + R[i] + h[i]);}std::cout << ans << '\n';}return 0;
}