手机网站开发入门,wordpress 插件 封面,上线一款app需要多少钱,徐汇制作网站哪家好传送门
题意#xff1a; 有 n 个怪兽需要消灭#xff0c;它们的生命值分别是 h [1],h [2]......h [n]. 我们可以使用两种技能#xff1a; 技能 1#xff1a;选择任意一个怪兽#xff0c;使其生命值降低 1 点#xff0c;并且需要 1 点能量值. 技能 2#xff1a;选择任意…传送门
题意 有 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.husing 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::vectorint h(n);for (int i 0; i n; i) {std::cin h[i];}std::vectorLL L(n);std::vectorLL R(n);for (int rot 0; rot 2; rot) {std::vectorstd::pairLL, 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;
}
