题意:有\(n\)个数,选\(k\)个数使得它们的和最大,选完某个数后,其相邻两个数不能再选.

题解:将所有数放到大根堆里,用双向链表来存顺序关系,对于堆顶的\(a_i\)来说,我们如果选了它,\(a_{i-1}\)和\(a_{i+1}\)就不能再选,但是\(a_{i-1}+a_{i+1}\)可能比\(a_i\)大,我们先不管,先将\(a_i\)贡献给答案,然后修改\(a_i=a_{i-1}+a_{i+1}-a_i\),并将\(a_{i-1}\)和\(a_{i+1}\)标记,修改顺序关系,使\(a_i\)和\(a_{i-2},a_{i+2}\)相连,当下次取到\(a_i\)时,说明我们需要反悔,即不应该选\(a_i\),而是要选\(a_{i-1}+a_{i+1}\),此时的\(a_i=a_{i-1}+a_{i+1}-a_i\),之前的\(ans+=a_i(original)\).所以这个\(a_i\)就消掉了,我们就反悔成功.

可能确实有点难理解,这里给个例子:\(7\ 8\ 6\ 9\ 6\).

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m;
struct link_list{
	int val;
	int l,r;
	int id;
	bool operator < (const link_list & fuck) const {
		return val<fuck.val;
	}
}pt[N];
priority_queue<link_list> h;
bool vis[N];

void dele(int x){
	pt[x].l=pt[pt[x].l].l;
	pt[x].r=pt[pt[x].r].r;
	pt[pt[x].l].r=x;
	pt[pt[x].r].l=x;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	rep(i,1,n){
		cin>>pt[i].val;
		pt[i].id=i;
		pt[i].l=i-1;
		pt[i].r=i+1;
		h.push(pt[i]);
	}

	pt[0].r=1,pt[n+1].l=n;

	ll ans=0;
	while(m--){
		while(vis[h.top().id]) h.pop();
		auto tmp=h.top();
		h.pop();
		if(tmp.val<=0) break;
		ans+=tmp.val;
		pt[tmp.id].val=pt[pt[tmp.id].l].val+pt[pt[tmp.id].r].val-pt[tmp.id].val;
		vis[pt[tmp.id].l]=vis[pt[tmp.id].r]=true;
		dele(tmp.id);
		h.push(pt[tmp.id]);
	}

	cout<<ans<<'\n';

    return 0;
}

l