【BZOJ2288】生日礼物 [贪心]

生日礼物

Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

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

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

Input

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

　　第2行， N 个整数 A, A, ..., A , 序列。

Output

　　一个整数，最大的和。

Sample Input

　　5 2
　　2 -3 2 -1 2

Sample Output

HINT

　　1 ≤ N ≤ 10， 0 ≤ M ≤ 10， 0 ≤ |A| ≤ 10

Solution

　　首先，我们可以把权值正负相同的连续的一段合并起来。Ans+=（所有正数），块数++。

　　然后把每一段的绝对值加入到小根堆里面。每次贪心取出最小的来，块数减去 1 直到满足题目要求为止。

　　为什么这样可以对呢？我们来讨论一下：

　　　　1. 如果删去的段是正数，那么相当于不取这个。

　　　　2. 如果删去的段是负数，那么相当于取了这个段合并它左右的两个段。

　　但是！这样会有一个问题！就是无法考虑连续取5个段及以上的情况，并且无法保证：取了一个数不取相连的两个数（会导致块数不减）。

　　所以判断一下，每次取段的时候，删去左右两个小段，加上一个大段（他们三个合并的值）即可。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int n, m;

 int a[ONE], A[ONE];

 int pre[ONE], suc[ONE];

 int Ans, block;

 struct power

 {

         int id, val;

         bool operator <(power a) const

         {

             return a.val < val;

         }

 };

 priority_queue <power> q;

 int get()

 {

         int res=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 int main()

 {

         n = get();    m = get();

         for(int i = ; i <= n; i++) a[i] = get();

         int from = ;    while(a[from] <= ) from++;

         int to = n;        while(a[to] <= ) to--;

         n = ;

         for(;from <= to;)

         {

             if( (a[from-] <=  && a[from] <= ) || (a[from-] >  && a[from] > ))

             A[n] += a[from];

             else A[++n] = a[from];

             from++;

         }

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

         {

             pre[i] = i - ;

             suc[i] = i + ;

             if(A[i] > ) Ans += A[i], block++;

             A[i] = abs(A[i]);

             q.push( (power){i, A[i]} );

         }

         if(block <= m) {printf("%d", Ans); return ;}

         pre[] = suc[n] = ;

         for(;;)

         {

             for(;;)

             {

                 power u = q.top();

                 if(u.val != A[u.id]) q.pop();

                 else break;

             }

             power u = q.top();    q.pop();

             Ans -= u.val;

             if(pre[u.id] == )    A[suc[u.id]] = INF, pre[suc[u.id]] = ;

             else

             if(suc[u.id] == )    A[pre[u.id]] = INF, suc[pre[u.id]] = ;

             else

             {

                 A[u.id] = A[pre[u.id]] + A[suc[u.id]] - A[u.id];

                 A[pre[u.id]] = A[suc[u.id]] = INF;

                 pre[u.id] = pre[pre[u.id]];

                 suc[u.id] = suc[suc[u.id]];

                 pre[suc[u.id]] = suc[pre[u.id]] = u.id;

                 q.push( (power){u.id, A[u.id]} );

             }

             block--;    if(block <= m) break;

         }

         printf("%d", Ans);

 }