https://www.luogu.org/problemnew/show/P1484

 

题解：本题其实是在n个数中选出至多k个数，且两两不相邻，并使所选数的和最大。

很容易想到动规思路：f[i][j]表示种到第i棵树且种了j棵的最大获利，则f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i])，注意边界、初始化即可。

但是，对于本题n<=300000的数据规模，动规显然不足以通过本题，需要另想算法。

我们先进行小规模枚举：

k=1时，显然取n个数中取最大的即可（暂不考虑全负的情况）。设最大的数是a[i]。

k=2时，则有两种可能：1、另取一个与a[i]不相邻的a[j]。2、取a[i-1]和a[i+1]。

我们可以发现：如果k=1时最优解为a[i]，那么我们便可以把a[i-1]和a[i+1]进行合并，因为它们要么同时被选，要么同时落选（证明不难，请自行解决）。而且，我们还注意到：当选了a[i-1]和a[i+1]时，获利便增加了a[i-1]+a[i+1]-a[i]。所以当a[i]被选时，我们就可以删去a[i-1]和a[i+1]，并把a[i]改成a[i-1]+a[i+1]-a[i]，重新找最大的。

每次找的都是最大的数，我们便可以使用堆进行操作，直到堆中最大值小于0或取出k个数后停止。复杂度O(klogn)。

 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=500000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k;
ll ans,cnt,flag,temp,sum;
int a[N],l[N],r[N];
bool vis[N];
char str;
struct node{
    ll id,x;
    bool operator <(const node&S)const{return x<S.x;}
}e;
priority_queue<node>q;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        e.x=a[i];
        e.id=i;
        l[i]=i-1;
        r[i]=i+1;
        q.push(e);
    }
    l[0]=1;
    r[n+1]=n;
    while(k--){
        while(vis[q.top().id])q.pop();
        e=q.top();
        q.pop();
        if(e.x<0)break;
        ans+=e.x;
        int id=e.id;
        e.x=a[id]=a[l[id]]+a[r[id]]-a[id];
        vis[l[id]]=vis[r[id]]=1;
        l[id]=l[l[id]];
        r[l[id]]=id;
        r[id]=r[r[id]];
        l[r[id]]=id;
        q.push(e);
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}