洛谷 P1484 种树（带悔贪心）

题目链接：

https://www.luogu.com.cn/problem/P1484

思路：

贪心的每次选择一个最大值种树，然后会发现如果选择了一个值，那么这个值两边的值都不能被选了。分析影响会发现，他两侧的值要么同时被选中，要么同时不被选中
例如： ……4 5 3……
当选择了5时，如果要调整成选择4的时候要么连3 一起选上，否则选择5一定是更优的选择。
因此考虑将5的影响消除，如果我们把这三个点都删掉，添加一个新的点 权值为 4+3-5，是不是就相当于没有选5而是选择了4和3.依次这样处理。将所有数放入大根堆，每次取出最大值维护，就能得到结果。

代码

#include<bits/stdc++.h> 
using namespace std;
const int maxi=1e6+7; 
typedef long long ll;
struct yhh{
    ll p;
    int id;
    bool operator<(const yhh &b) const{//定义排序方式 
        return p < b.p;
    }
};
int n,k,pre[maxi],nxt[maxi],del[maxi];
ll P[maxi];
priority_queue<yhh> q;
int main()
{
    scanf("%d%d", &n,&k);
    pre[0]=0,nxt[0]=1;
    pre[n+1]=n,nxt[n+1]=n+1;
    for (int i=1;i<=n;++i)
    {
        scanf("%lld",&P[i]);
        q.push(yhh{P[i],i});//将权值和位置放进队列 
        pre[i]=i-1,nxt[i]=i+1;//记录前驱和后继 
    }
    ll res=0;//统计权值 
    for(int i=0;i<k;++i)
    {
        while(del[q.top().id])//如果这个点已经被删掉了 
            q.pop();
        if(q.top().p<=0)//小于0的点很明显不需要取 
            break;
        yhh t=q.top();//取队头 
        q.pop();
        res+=t.p;//增加权值 
        P[t.id]=P[pre[t.id]]+P[nxt[t.id]]-P[t.id];//将三个点合成一个点 
        del[pre[t.id]]=del[nxt[t.id]]=1;//将选中的点两边的点都删除 
        pre[t.id]=pre[pre[t.id]],nxt[t.id]=nxt[nxt[t.id]];//更新这个点的前驱和后继 
        nxt[pre[t.id]]=t.id,pre[nxt[t.id]]=t.id;//更新旁边点的前驱和后继 
        q.push(yhh{P[t.id],t.id});//将这个点重新塞进优先队列 
    }
    printf("%lldn", res);//输出答案 
    return 0;
}

此处有一个小问题就是如果出现了负数权值，是不能被选择的，因为会导致结果变小。

最后

以上就是发嗲台灯为你收集整理的洛谷 P1484 种树（带悔贪心）的全部内容，希望文章能够帮你解决洛谷 P1484 种树（带悔贪心）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。