「Bzoj 2288」生日礼物 (链表+堆)

BZOJ 2288
题意:给出一个长度为$n$的数列,要求从中取出不超过$m$段连续的数,使其和最大。

首先压缩,将符号相同的压成一个元素,0随意放在任意一块位置,那么序列变为一正一负交错序列。
然后考虑没有限制$m$时,选所有正数即可。
如果有限制,我们就可以抛弃某些正数或者加入某些负数使得两个正数合成一块(注意头尾的负数不能取)
我们发现不管负数正数都只关心他的绝对值
然后对于每次操作的点他左右两边的点都是不能取的,所以转化到了Bzoj 1150

链表堆维护即可。注意记录值只需要绝对值,包括之后的任何操作!

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int abss(int x) {return x > 0 ? x : -x;}
struct data {
int u, val;
bool operator < (const data &rhs) const {return val > rhs.val;}
};
priority_queue<data > q;
int n, m, a[MAXN];
int nn, b[MAXN];
int tot, h, t, l[MAXN], r[MAXN], val[MAXN], vis[MAXN];
void ins(int pos, int v) {
++tot, val[tot] = v;
l[r[pos]] = tot;
r[tot] = r[pos], l[tot] = pos;
r[pos] = tot;
}
void del(int pos) {
vis[pos] = 1;
r[l[pos]] = r[pos], l[r[pos]] = l[pos];
}
void clean() {
ms(vis, 0);
tot = 1, h = 0, t = 1;
l[t] = h, r[h] = t, val[0] = val[1] = 1000000002;
}
int solve() {
clean();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
nn = -1;
int now = 0, tjz = 0, totz = 0;
for (int i = 1; i <= n; ++i) {
if (i == 1 || a[i] * now < 0) {
b[++nn] = now;
if (now > 0) ++tjz, totz += now;
now = 0;
}
now += a[i];
}
if (now > 0) ++tjz, totz += now;
b[++nn] = now;
int hh = 1;
if (b[1] < 0) ++hh;
if (b[nn] < 0) --nn;
ins(h, b[hh]), q.push((data){tot, abss(b[hh])});
for (int i = hh + 1; i <= nn; ++i) ins(tot, b[i]), q.push((data){tot, abss(b[i])});
int nd = tjz - m;
if (nd <= 0) return cout << totz << endl, 0;
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue ;
if (val[p.u] < 0 && ((l[p.u] == h) || (r[p.u] == t))) continue ;
totz -= p.val;
val[p.u] = abss(val[l[p.u]]) + abss(val[r[p.u]]) - abss(val[p.u]);
if (l[p.u] != h || l[p.u] != t) del(l[p.u]);
if (r[p.u] != h || r[p.u] != t) del(r[p.u]);
q.push((data){p.u, abss(val[p.u])});
--nd;
if (!nd) break ;
}
return cout << totz << endl, 0;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------