2288: 【POJ Challenge】生日礼物

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

分析：

　　贪心+堆+链表。

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

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

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

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

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

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<cctype>

 #include<set>

 #include<queue>

 #include<vector>

 #include<map>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 const int INF = 1e9;

 struct Node{

     int x, id;

     Node() {}

     Node(int a,int b) { x = a, id = b; }

     bool operator < (const Node &A) const {

         return x > A.x;

     }

 };

 priority_queue< Node > q;

 int pre[N], nxt[N], vis[N], a[N], b[N];

 int cnt;

 void del(int x) {

     if (!x || x == cnt + ) return ;

     vis[x] = ;

     b[x] = INF;

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

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

 }

 int main() {

     int n = read(), m = read(); cnt = ;

     b[] = a[] = read();

     int last = a[];

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

         a[i] = read();

         if (a[i] == ) continue;

         if (a[i] * last < ) b[++cnt] = a[i];

         else b[cnt] += a[i];

         last = a[i];

     }

     if (b[cnt] < ) cnt --;

     if (b[] < ) { cnt --; for (int i = ; i <= cnt; ++i) b[i] = b[i + ]; }

     int ans = , d = ;

     for (int i = ; i <= cnt; ++i) {

         if (b[i] > ) ans += b[i], d ++;

         else b[i] = -b[i];

         q.push(Node(b[i], i));

     }

     if (d <= m) { cout << ans << " "; return ; }

     else d = d - m;

     b[] = INF, b[cnt + ] = INF;

     for (int i = ; i <= cnt + ; ++i) nxt[i] = i + , pre[i] = i - ;

     pre[] = ; nxt[cnt + ] = cnt + ;

     while (d --) {

         while (vis[q.top().id]) q.pop();

         Node now = q.top(); q.pop();

         int i = now.id; ans -= now.x;

         int t = min(INF, b[pre[i]] + b[nxt[i]] - now.x);

         del(pre[i]), del(nxt[i]);

         b[i] = t; q.push(Node(b[i], i));

     }

     cout << ans;

     return ;

 }