真.调查兵团的种树式 100分解法

· · 题解

该不会真又有人点了之前的100分做法吧

做法

本题第一个思路是贪心，然而常规贪心无法解决不相邻的问题，所以就有了50分的dp做法，此时我们想到只要建立一个大根堆并保证每次出堆后，根顶元素互不相邻，然后累加权值就可以了。

但这么做显然有问题，所以可以把上述思路优化成如果我先取了一个较大的点后来发现取相邻两个点比只取它一个更优那就取相邻的那两个点，

so：两种情况

我们如何才能取到上述情况呢，可以先把每个a_i放进堆中，每次取出最大值后 ans+=a[i] 再将a[i-1]+a[i+1]-a[i]放入堆中,如果后来堆顶取到它就代表取相邻两点更优

再再再考虑到可能取相邻的相邻更优所以每次我们将a[i-1]+a[i+1]-a[i]放入堆中时将a_i相邻两点打上标记视为删除，将a_i=a[i-1]+a[i+1]-a[i]，更改其余点的相邻情况，确保其他点不会取到a_i相邻的两个点就行

实现： 可使用链表进行维护

可能讲得相当模糊，大家看代码吧。同大家也可以通过模拟代码，来理解这道题（因为我讲得太烂了）

代码

#include<cstdio>
#include<queue>
using namespace std;
long long n,m;
long long arr[300005];
struct s{
    long long num;
    long long id;
};
priority_queue <s> q;
bool operator<(s x,s y){
    return x.num<y.num;
}
long long l[300005],r[300005];
long long t[300005];
long long ans;
int main(){
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++){
        scanf("%lld",&arr[i]);
        l[i]=i-1;
        r[i]=i+1;
        q.push({arr[i],i});
    }
    l[n+1]=n;
    r[0]=1;
    for(long long i=1;i<=m;i++){
        while(t[q.top().id]==1){
            q.pop();
        }
        if(q.top().num<=0){
            break;
        } 
        long long wei=q.top().num;
        long long poi=q.top().id;
        q.pop();
        arr[poi]=arr[l[poi]]+arr[r[poi]]-arr[poi];//提供反悔选项 
        q.push({arr[poi],poi});
        t[l[poi]]=1;//标记 
        t[r[poi]]=1;
        l[poi]=l[l[poi]];//更新相邻情况，注意相邻的相邻也要更新 
        r[poi]=r[r[poi]];
        r[l[poi]]=poi;
        l[r[poi]]=poi;
        ans+=wei;
    }
    printf("%lld",ans);
    return 0;
}

讲得很烂，代码也很丑，大家凑合着看吧orz。 分享两个大佬的题解：

思路看的这篇

代码c的这篇，这篇的思路也很好

题外话

看了大佬们的题解后才发现这类题目叫反悔贪心，贪心思路好似和之前的“糖果”有点像。

个人认为本题贪心策略可以学习，链表维护不相邻的情况也可以学习，但放在一起适用性并不高