2288: 【POJ Challenge】生日礼物

https://lydsy.com/JudgeOnline/problem.php?id=2288

分析：

　　贪心+堆+链表。

　　首先把序列变一下，把相邻的同符号的合并起来，让序列的第一个是整数，最后一个也是整数。

　　如果直接算最大的选的不好算，那么考虑算最小的不选的，正难则反。

　　然后把所有的整数都加起来，这就是最大的共和。如果此时的段数<=m，那么直接输出就好了。否则，需要选几个数字，来合并它左右的段，以此是段的总数-1。

　　选的是一个负数，表示，左边的段后右边的段经过这个负数合起来了。选的是一个正数，那么表示这个正数不要了。由于减去的都是绝对值的大小，那么可以把序列变成正的。此时问题转化为，选k个数，使得它们的和最小，并且不能相邻。

　　然后用堆+链表维护。类似上一道题。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<cctype>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 
14 inline int read() {
15     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
16     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
17 }
18 
19 const int N = 200005;
20 const int INF = 1e9;
21 
22 struct Node{
23     int x, id;
24     Node() {}
25     Node(int a,int b) { x = a, id = b; }
26     bool operator < (const Node &A) const {
27         return x > A.x;
28     }
29 };
30 priority_queue< Node > q;
31 int pre[N], nxt[N], vis[N], a[N], b[N];
32 int cnt;
33 
34 void del(int x) {
35     if (!x || x == cnt + 1) return ;
36     vis[x] = 1;
37     b[x] = INF;
38     nxt[pre[x]] = nxt[x];
39     pre[nxt[x]] = pre[x];
40 }
41 
42 int main() {
43     int n = read(), m = read(); cnt = 1;
44     
45     b[1] = a[1] = read();
46     int last = a[1];
47     for (int i = 2; i <= n; ++i) {
48         a[i] = read();
49         if (a[i] == 0) continue;
50         if (a[i] * last < 0) b[++cnt] = a[i];
51         else b[cnt] += a[i];
52         last = a[i];
53     }
54     if (b[cnt] < 0) cnt --;
55     if (b[1] < 0) { cnt --; for (int i = 1; i <= cnt; ++i) b[i] = b[i + 1]; }
56     int ans = 0, d = 0;
57     for (int i = 1; i <= cnt; ++i) {
58         if (b[i] > 0) ans += b[i], d ++;
59         else b[i] = -b[i];
60         q.push(Node(b[i], i));
61     }
62     if (d <= m) { cout << ans << " "; return 0; }
63     else d = d - m;
64     
65     b[0] = INF, b[cnt + 1] = INF;
66     for (int i = 0; i <= cnt + 1; ++i) nxt[i] = i + 1, pre[i] = i - 1;
67     pre[0] = 0; nxt[cnt + 1] = cnt + 1;
68     
69     while (d --) {
70         while (vis[q.top().id]) q.pop();
71         Node now = q.top(); q.pop();
72         int i = now.id; ans -= now.x; 
73         int t = min(INF, b[pre[i]] + b[nxt[i]] - now.x);
74         del(pre[i]), del(nxt[i]);
75         b[i] = t; q.push(Node(b[i], i));
76     }
77     cout << ans;
78     return 0;
79 }