洛谷P1484.种树

洛谷P1484.种树

题目解析及思路

题目要求在一条n个坑的路上，对于已知每个坑种树的收益，并且相邻两个坑不能同时种树的情况下，求最大收益

思考一个小范围的例子(不考虑数组全负数)：

• 当m = 1时，答案一定为数组中的最大数，假设为a[i]
• 当m = 2时，答案有两种情况：1.仍取a[i]，且再取一个其他不相邻的元素
  2.不取a[i]，改为取a[i-1]和a[i+1](同取或同不取)

因此可以用一个堆将所有数据加入，如果k=1时最优解为a[i]，那么我们便可以把a[i-1]和a[i+1]进行合并

同时将a[i]改成a[i-1]+a[i+1]-a[i]，继续找最大的，直到最大值<=0或取完k个

**反悔贪心：**因为a[i-1]+a[i+1] > a[i]时，我们要取a[i-1]和a[i+1]而不是a[i]，因此在改为a[i-1]+a[i+1]-a[i]时，如果再取到a[i-1]+a[i+1]-a[i]，a[i-1]+a[i+1]-a[i] + a[i] = a[i-1]+a[i+1] 可以实现找更优情况

参考题解

代码

#include<bits/stdc++.h>

using namespace std;
#define PII pair<int, int>
typedef long long LL;
const int N = 300010;

bool st[N];
//lr分别存左右两边的下标，更新方式参考链表
int l[N],r[N],a[N];
//优先队列存对组，记录下标
priority_queue<PII> q;
LL n,m,res;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        //优先队列存对组，记录下标
        scanf("%d", &a[i]);
        q.push(make_pair(a[i],i));
        //记录左右下标
        l[i] = i-1,r[i] = i+1;
    }
    //哨兵
    r[0] = 1,l[n+1] = n;
    while(m --)
    {
        //左右两边的元素被去掉了不遍历
        while(st[q.top().second])
            q.pop();
        PII tmp = q.top();
        q.pop();
        if(tmp.first <= 0) break;
        res += tmp.first;
        //取当前下标
        int pos = tmp.second;
        //把反悔值改进来
        a[pos] = a[l[pos]] + a[r[pos]] - a[pos];
        tmp.first = a[pos];
        //把两边去掉，标记成true
        st[l[pos]] = st[r[pos]] = 1;
        //更新左右"链表"
        l[pos] = l[l[pos]], r[l[pos]] = pos;
        r[pos] = r[r[pos]], l[r[pos]] = pos;
        q.push(tmp);
    }
    cout<<res<<endl;
}