526互联

codeforces 1795E Explosions?

发布时间 2023-04-05 23:29:58作者: 冯文健

https://codeforces.com/problemset/problem/1795/E

解题思路

问题的核心是要构造有一个先严格递增，然后严格递减的子序列。不在这个序列中的怪物单独击杀。先递增后递减可以看作是两个对称的问题，所以把递增序列的构造考虑清楚就可以了。

假设已经知道将1～i-1构造成严格递增子序列所需要的花费是L[i-1]（注意：这里讲的严格递增子序列是指进行构造后并排除了序列1～i-1中前导0的部分）。

如果h[i] > h[i-1]，那么L[i] = L[i-1]。

如果h[i] <= h[i-1]，那就需要对前i-1个元素进行操作，让序列重新成为严格递增子序列。此时L[i] = L[i-1] + 新操作的花费。

由于序列1～i-1已经是严格递增子序列了，计算新花费朴素的做法是从位置i-1开始向左回溯，每次比较当前位置和后一个位置元素的大小，计算操作当前位置元素所需花费。这种方法整个程序的时间复杂度是O(n2)会超时，得优化这个计算过程。

考虑能否通过某种途径进行整体计算，而不必对1～i-1的每个元素都进行回溯。观察到此时i-1处的元素的值要更新为h[i]-1，在这之后h[i-1]和h[i]就变成了一个严格递增子序列并且序列的公差为1。由于子序列1~i-1也是通过这种方式构建的，所以子序列1~i-1是由若干个公差为1的严格递增子序列构成的（可以通过递推的视角进行思考）。有了这个性质，现在就只需要对这若干个公差为1的子序列进行整体操作了，而不用对每个元素进行回溯。这样的序列只需要记录最大值和序列长度就可以了。进行整体运算的时候注意元素不能扣成负数。程序的整体时间复杂度是O(n)。

/* https://codeforces.com/problemset/problem/1795/E */
#include <bits/stdc++.h>
using namespace std;

#define N 300001

int64_t L[N], R[N], ans;
int t, n, h[N], ptr;
struct node {
    int num;
    int64_t h;
} st[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> h[i];
        }
        if (1 == n) {
            cout << h[0] << endl;
            continue;
        }

        // 从左到右
        st[0].h = h[0];
        st[0].num = 1;
        ptr = 0;
        L[0] = 0;
        for (int i = 1; i < n; i++) {
            int num = 1; // 当前区间(h[i], num)
            L[i] = L[i-1];
            // 合并区间
            while(ptr >= 0 && h[i]-num < st[ptr].h) {
                int len = min(st[ptr].num, h[i]-num);
                L[i] += len * (st[ptr].h - (h[i]-num));
                if (len < st[ptr].num) {
                    L[i] += ((st[ptr].h - st[ptr].num + 1) + (st[ptr].h - len)) * (st[ptr].num - len) / 2;
                }
                num += len;
                ptr--;
            }
            ptr++;
            st[ptr].h = h[i];
            st[ptr].num = num;
        }

        // 从右到左
        st[0].h = h[n-1];
        st[0].num = 1;
        ptr = 0;
        R[n-1] = 0;
        for (int i = n-2; i >= 0; i--) {
            int num = 1; // 当前区间(h[i], num)
            R[i] = R[i+1];
            // 合并区间
            while(ptr >= 0 && h[i]-num < st[ptr].h) {
                int len = min(st[ptr].num, h[i]-num);
                R[i] += len * (st[ptr].h - (h[i]-num));
                if (len < st[ptr].num) {
                    R[i] += ((st[ptr].h - st[ptr].num + 1) + (st[ptr].h - len)) * (st[ptr].num - len) / 2;
                }
                num += len;
                ptr--;
            }
            ptr++;
            st[ptr].h = h[i];
            st[ptr].num = num;
        }

        ans = INT64_MAX;
        for (int i = 0; i < n; i++) {
            ans = min(ans, L[i]+R[i]+h[i]);
            //cout << "..." << L[i] << " " << R[i] << " " << h[i] << endl;
        }
        cout << ans << endl;

    }
    return 0;
}