题解 P1484 种树

题目

传送门

思路

开始没有想到，这是一道可以反悔的贪心题。

我们可以用大根堆来维护最大获利的树，用链表来维护每棵树左右的树。

每次选择了最大的树，我们要把此树左右两边 vis 标记为1，下次枚举到vis[x] = 1时 continue。

但有可能选左右两颗树比选中间这颗树情况更优，于是我们要在加入一颗树，值为 左树权值+右树权值-中间树权值。

这样，在下一次枚举时，当我们选了这颗树，则答案增加了 左树权值+右树权值-中间树权值+中间树权值 = 左树权值+右树权值。 正好选择了2颗树。

注意：不一定要种满 k 颗树

代码

#include <cstdio>

#include <iostream>

#include <queue>

#include <algorithm>

#include <vector>

#include <cstring>

#include <string>

#define ll long long

#define mes(x) memset(x,0,sizeof(x))

#define re(x) read(x)

#define il inline

using namespace std;

template <typename T>

il void read(T &x){

	x = 0; T sgn = 1; char ch = getchar();

	for(;!isdigit(ch);ch = getchar()) if(ch=='-') sgn = -1;

	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);

	x *= sgn;

}

template <typename T>

il void write(T x){

	if(x < 0) x = -x,putchar('-');

	if(x == 0) putchar(48);

	int cnt = 0, a[70];

	while(x > 0){

		a[++cnt] = x%10;

		x /= 10;

	}

	for(int i = cnt;i > 0;i--){

		putchar(a[i]+48);

	}

	putchar('\n');

}

const int MAXN = 5e5+10;

int n,k,a[MAXN];

bool vis[MAXN];

ll ans = 0,tot = 0;

struct tree{

	int pos;

	ll val;

	bool operator < (const tree &b) const {

		return val < b.val;

	}

}tr[MAXN];

struct place{

	int l,r;

	ll val;

}p[MAXN];

priority_queue <tree> q;

il void Del(int x){

	p[x].l = p[p[x].l].l;

	p[x].r = p[p[x].r].r;

	p[p[x].l].r = x;

	p[p[x].r].l = x;

}

int main (){

	re(n);re(k);

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

		re(a[i]);

		p[i].l = i-1;

		p[i].r = i+1;

		p[i].val = a[i];

		q.push((tree){i,a[i]});

	}

    for(int i = 0;i < k;i++){

    	int x = q.top().pos; q.pop();

    	if(vis[x]) {

    		i--;

    		continue;

    	}

    	vis[p[x].l] = vis[p[x].r] =1;

		tot += p[x].val;

		ans = max(tot,ans);

		p[x].val = p[p[x].l].val + p[p[x].r].val - p[x].val;

		q.push((tree){x,p[x].val});

		Del(x);

	}

	write(ans);

	return 0;

}