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