首页 > 其他分享 >codeforces 1795E Explosions?

codeforces 1795E Explosions?

时间:2023-04-05 23:35:39浏览次数:47  
标签:int codeforces len st num Explosions 序列 ptr 1795E

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

 

标签:int,codeforces,len,st,num,Explosions,序列,ptr,1795E
From: https://www.cnblogs.com/fwjonair/p/17291169.html

相关文章

  • Codeforces Round 862 (Div. 2)
    CodeforcesRound862(Div.2)链接CodeforcesRound862(Div.2)A题#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vector>#include<cstring>#include<unordered_set>#includ......
  • Codeforces Round 863 (Div. 3)
    CodeforcesRound863(Div.3)链接CodeforcesRound863(Div.3)A题遍历这个字符串,如果要插入的数第一次小于当前的数,就将数插入到这里,如果到最后都没有插入数,插入到最后#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vec......
  • Codeforces Round 863 (Div. 3) E题
    题目地址题意:定义数组a包含所有不含数字4的正整数,给出一个n,要求求出数组a中第n个数Solution数位dp+二分,求出[1,mid]中不含数字4的正整数个数,不过因为有可能mid包含4,但是由于贡献是一样的,可以直接把4都变成3,最后处理一下即可intdp[20];inta[20];voidinit(){ dp[0]=1; f......
  • Codeforces Round 863 (Div. 3)
    A.InsertDigit放在第一个比他小的数前面#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,d;cin>>n>>d;strings;cin>>s;for(chari:s){if(d>i-'0')cout<<d,d......
  • Codeforces Round 640 (Div. 4) ABCDEFG
    https://codeforces.com/contest/1352不知道怎么的复制过来的代码容易歪,观看效果可能不大好。这场古早div4,大题极其友好,除了E卡空间卡到我爆炸,别的都体验感极好。A.SumofRoundNumbers#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpai......
  • Codeforces Round 863 (Div. 3) A-C 赛后思路复盘
    A(思维)思路:观察样例可知数越大放在前面越优。遍历字符串,判断当前位置的数字和要插入的数字的关系,如果要插入的数大于当前数,那么就插入到当前数的前面。string里有一个insert函数,可以把指定字符串插入到指定下标之前。在原串下标为pos的字符前插入字符串strbasic_string&insert......
  • codeforces round 862
    A.和洛谷上的删数思路一致,后者是找峰顶,这个是找谷底从前到后枚举每一位与要添加的数比大小,如果要添加的数<=该位的数,就继续枚举,否则就将这个数添加在其前面B.需要移动的步数=两个点所在的层数之差的绝对值,只要计算出所在层数就可以一开始没想明白怎么算这个层数,先把每个......
  • Codeforces Round 861 (Div. 2)
    Preface这场感觉都是一个礼拜前补题打的了,但由于上周末事情比较多都没来得及写题解因此可能题意都记得不是很清楚了,就简略地谈一谈吧A.LuckyNumbers不难想到直接暴力从左端点枚举到右端点并对每个数进行暴力判断一个很naive的结论就是当答案为\(9\)时直接输出即可,然后我们......
  • Codeforces Round 862 A-E
    CodeforcesRound862(Div.2)先简单写一下A-E的题解。A异或的经典性质:\(x\oplusx=0\)。B显然要把字典序最小的那个字母放到最前面。如果这个字母出现了很多次,那么应该选择最后一次出现的位置。这也很容易证明。C联立以后计算一下就行了。比赛的时候爆了一次int。......
  • Codeforces Round 717 (Div. 2) B. AGAGA XOOORRR(位运算)
    https://codeforces.com/contest/1516/problem/B题目大意:给定长度为n的数组a,问我们能不能一直选择两个相邻的元素进行异或后,删除这两个值,把异或值留下来,最后剩下>=2个数字,它们都是相同的?可以做到输出YES,不能的话输出NO。input23022423110outputYESNO题......