题解 P1484 【种树】

· · 题解

P1792题解

传送门

题意简述

给出一个 n 个有权值节点的链，选出 k 个不相邻的节点，使它们的权值和最大。

n<=5*10^5 , k<=n/2

题目分析

如果 k = 1，那么结果就是a数组中的最大值。

如果 k = 2，那么就有两种情况：

  1. 选择最大值 a_i ，不选 a_{i-1} ,a_{i+1} ，再从剩下的数中选择最大值。
  2. 不选最大值 a_i ，选 a_{i-1} ,a_{i+1} 。

为什么不选最大值 a_i 就要选 a_{i-1} ,a_{i+1} 呢？

如果只选了 a_{i-1} ,a_{i+1} 中的一个，那么把选了的换成了 a_i 一定更优。

显然a_i , a_{i-1} ,a_{i+1} 都不选不是最优解。

所以最小值左右两侧的数要么都选，要么都不选。

所以我们可以先选上 a 数组中的最大值（第一种情况），然后将然后将 a_{i-1},a_i,a_{i+1} 从数列中删除，并在原位置插入一个新元素a_{i-1}-a_i+a_{i+1} 。这样原问题就变成了一个从 a数组中选 k-1 的数的子问题，显然重复这个操作 k-1次就可以求出最终结果。

代码实现思路

所以我们可以建立一个链表 Q，分别记录a_1,a_2,a_3 … a_{N-1} 。 再建立一个二元组大根堆，每个元素与链表中的每一个元素成一一映射关系，第二元记录对应链表中的指针。

每次取出堆顶，更新答案。再删除节点（链表中打标记、更新左右节点数组，大根堆中删除）、插入新节点。

执行K次后输出。

易错点

AC代码

内带详细注释

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 500010
#define ll long long
using namespace std;
void read(ll &x){
    int f=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
ll a[N],le[N],r[N];
long long ans;
bool v[N];
priority_queue < pair < ll , ll > > q;
void del(int x){//删除操作 
    le[r[x]]=le[x];
    r[le[x]]=r[x];
    v[x]=1;//节点是否删除 
}
int main(){
    int n,m;
    cin>>n>>m;
    //le[1]=n;r[1]=2;le[n]=n-1;r[n]=1;
    for(int i=1;i<=n;i++){
        read(a[i]);//读入 
    }
    for(ll i=1;i<=n;i++) le[i]=i-1,r[i]=i+1;//建立链表 
    for(ll i=1;i<=n;i++){
        q.push(make_pair(a[i],i));//第一元为值，第二元为标号 
    }
    while(m--){
        int x,y;
        while(v[q.top().second]) q.pop();
        y=q.top().second;q.pop();//取出最大节点 
        if(a[y]<0) break;
        ans+=a[y];//更新答案 
        a[y]=a[le[y]]+a[r[y]]-a[y];//新节点 
        del(le[y]);del(r[y]);//删除 
        q.push(make_pair(a[y],y)); 
    }
    printf("%lld\n",ans);
    return 0;
}