题目描述
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, …, AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？
分析
这道题目还是非常简单的，和数据备份几乎是一样的，吐槽完毕。
参照之前我们的思路，因为是m段不同的部分，那么很明显，一段全是同一符号的一定是一起被一起选走，那么我们首先将原序列变换成只有正负交叉的序列，这样保证了我们能够一次就拿掉整个区间。
因为我们需要让和最大，那么有两种情况：
- 正数区间
- 正数区间+负数区间+...
那么我们思考一个贪心，如果一个正数区间非常的大，那么我们一定会选择这个区间，反之如果一个区间非常的小，也就是负数非常的大，那么我们就一定不会选择这个区间。从中显然推出我们需要按照绝对值排序，排序过程用优先队列来实现。
如果一开始正数区间个数就小于了m个，那么就可以直接不用遍历，反之我们需要去掉一些区间：
那么如果选正数，就意味着不选这个数，也就是直接删掉，因为后面还有更优的答案，tot-1。
如果选的是负数，说明左右区间合并，因为我们是绝对值较小，那么对于我们答案的影响一定是最小的，那么tot-1，合并区间。
否则那么就tot+1。
合并区间的操作和数据备份是一样的：https://www.cnblogs.com/chhokmah/p/10557925.html。
ac代码
#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define N 100005
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') fl = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= fl;
}
struct node {
int id, val;
node(int id, int val): id(id), val(val){}
bool operator <(const node &rhs) const {
return abs(val) > abs(rhs.val);
}
};
int a[N], b[N], lst[N], nxt[N];
priority_queue<node> q;
int tot, n, m, ans;
bool vis[N];
void remove(int x) {
vis[x] = 1;
lst[nxt[x]] = lst[x];
nxt[lst[x]] = nxt[x];
}
int main() {
memset(vis, 0, sizeof(vis));
read(n); read(m);
for (int i = 1; i <= n; i ++) read(b[i]);
tot = 1;
for (int i = 1; i <= n; i ++) {
if ((ll)a[tot] * b[i] >= 0) a[tot] += b[i];
else a[++ tot] = b[i];
}
n = tot;
tot = 0;
for (int i = 1; i <= n; i ++) {
if (a[i] > 0) tot ++, ans += 1ll * a[i];
}
for (int i = 1; i <= n; i ++) {
nxt[i] = i + 1;
lst[i] = i - 1;
q.push(node(i, a[i]));
}
while (tot > m) {
tot --;
while (vis[q.top().id]) q.pop();
int x = q.top().id;
q.pop();
if (lst[x] != 0 && nxt[x] != n + 1) ans -= abs(a[x]);
else if (a[x] > 0) ans -= a[x];
else {
tot ++;
continue;
}
a[x] = a[lst[x]] + a[nxt[x]] + a[x];
remove(nxt[x]);
remove(lst[x]);
q.push(node(x, a[x]));
}
printf("%d\n", ans);
return 0;
}