BZOJ2288 【POJ Challenge】生日礼物【堆 + 链表】

题目

ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。

自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？

输入格式

第1行，两个整数 N (1 ≤ N ≤ 105) 和 M (0 ≤ M ≤ 105), 序列的长度和可以选择的部分。

第2行， N 个整数 A1, A2, ..., AN (0 ≤ |Ai| ≤ 104), 序列。

输出格式

一个整数，最大的和。

输入样例

5 2

2 -3 2 -1 2

输出样例

题解

我们把连续的同号元素合并

得到的序列就是正负交错的序列

加入正数数量<=m，全部选掉就是答案

若正数数量>m，就对于某些数意味着

①不选该正数

②多选一个负数使得相邻正数相连，这样相当于可以少放弃一个正数

我们先将正数总和求出来

然后将所有数的绝对值加入小根堆

每次选出一个减去，然后与邻近的合并【就像选m个不相邻的数和最小一样】

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define LL long long int

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

#define ls (u << 1)

#define rs (u << 1 | 1)

#define fa (u >> 1)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int pre[maxn],nxt[maxn],val[maxn],n,m,A[maxn],V[maxn],tot,cnt;

struct node{int v,u;}H[2 * maxn];

int hsiz,pos[2 * maxn];

int pd(int u){

	int small;

	while (true){

		small = u;

		if (ls <= hsiz && H[ls].v < H[small].v) small = ls;

		if (rs <= hsiz && H[rs].v < H[small].v) small = rs;

		if (small != u){

			pos[H[small].u] = u; pos[H[u].u] = small;

			swap(H[small],H[u]);

			u = small;

		}else break;

	}

	return u;

}

void pup(int u){

	while (u > 1 && H[fa].v > H[u].v){

		pos[H[fa].u] = u; pos[H[u].u] = fa;

		swap(H[fa],H[u]);

		u = fa;

	}

}

void ins(int u){

	H[++hsiz] = (node){val[u],u}; pos[hsiz] = u;

	pup(hsiz);

}

void del(int u){

	pos[H[hsiz].u] = u;

	swap(H[u],H[hsiz--]);

	u = pd(u);

	pup(u);

}

int main(){

	n = read(); m = read();

	REP(i,n){

		A[++tot] = read();

		if (!A[tot]) tot--;

	}

	int x = 1;

	while (A[x] < 0 && x <= tot) x++;

	if (x > tot) {puts("0"); return 0;}

	V[n = 1] = A[x];

	while (A[tot] < 0 && tot) tot--;

	if (!tot) {puts("0"); return 0;}

	for (int i = x + 1; i <= tot; i++){

		if ((A[i] < 0 && A[i - 1] < 0) || (A[i] > 0 && A[i - 1] > 0))

			V[n] += A[i];

		else V[++n] = A[i];

	}

	cnt = n / 2 + 1;

	if (cnt <= m){

		sort(V + 1,V + 1 + n);

		int ans = 0;

		for (int i = 0; i < cnt && V[n - i] > 0; i++) ans += V[n - i];

		printf("%d\n",ans);

	}else {

		int ans = 0;

		for (int i = 1; i <= n; i++){

			if (V[i] > 0) ans += V[i];

			val[i] = abs(V[i]);

			if (i > 1) pre[i] = i - 1;

			if (i < n) nxt[i] = i + 1;

			ins(i);

		}

		int t = cnt - m,x; node u;

		while (t--){

			u = H[1]; x = u.u;

			ans -= u.v;

			if (!pre[x]){

				del(1); del(pos[nxt[x]]);

				pre[nxt[nxt[x]]] = 0;

			}else if (!nxt[x]){

				del(1); del(pos[pre[x]]);

				nxt[pre[pre[x]]] = 0;

			}else {

				int l = pre[x],r = nxt[x];

				del(pos[l]); del(pos[r]);

				H[1].v = val[x] = val[l] + val[r] - val[x]; pos[x] = 1;

				pd(1);

				nxt[pre[x] = pre[l]] = x;

				pre[nxt[x] = nxt[r]] = x;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

BZOJ2288 【POJ Challenge】生日礼物【堆 + 链表】

题目

输入格式

输出格式

输入样例

输出样例

题解

最新文章

热门文章

巴特西

BZOJ2288 【POJ Challenge】生日礼物 【堆 + 链表】

题目

输入格式

输出格式

输入样例

输出样例

题解

最新文章

热门文章

BZOJ2288 【POJ Challenge】生日礼物【堆 + 链表】