真的是假的吗?

题解 P1792 【[国家集训队]种树】
题解

诶,没人发题解吗

这道题好像和编译优化是重题。。

刚看到这题第一反应是DP。。然而瞅了一眼数据范围(emm,200000),这要是DP空间炸飞啊。。

于是。。于是就又深入思考 看了一个dalao的blog

发现是一个贪心。。思路非常神奇。。

就是以在每个坑种树的收益建一个大根堆

然后用链表存它的前驱后继(n的后继为1,1的前驱为n)

每次取最大的收益。

那么问题来了————有可能在这个点种树比在它两边各种一棵树收益小。

但一定是两边各种一棵,因为我们建的是大根堆,先出来的一定大。

所以我们可以选这个坑种树,也可以选两边的坑各种一棵,所以我们给我们的贪心一个反悔的机会

就是选在这个坑种树以后将它两边的坑合并为一个价值为(w[l]+w[r]-w[now])的坑,代替我们选择的坑

这里非常的巧妙,就是如果选了这个坑就相当于不在那个中间的坑种树了,而是在它两边各种一棵。

然后放一下丑陋的代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
# define M (200000+50)
using namespace std;
struct node{
    int value,place;
    friend bool operator < (node x,node y){
        return x.value < y.value;
    }
};
priority_queue<node> q;
int n,m,Ans,chose,nxt[M],pre[M],w[M],l,r;
bool vis[M];
void change(int x){
    vis[x]=1;
    nxt[pre[x]]=nxt[x];
    pre[nxt[x]]=pre[x];
    nxt[x]=0; pre[x]=0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)  {
      scanf("%d",&w[i]);
    }
    if((n>>1)<m){
        cout<<"Error!"<<endl;
        return 0;
    }
    for(int i=1;i<n;i++) nxt[i]=i+1; nxt[n]=1;
    for(int i=2;i<=n;i++) pre[i]=i-1; pre[1]=n;
    for(int i=1;i<=n;i++) q.push((node){w[i],i});
    for(int i=1;i<=m;i++){
        while(vis[q.top().place]) q.pop() ;
        node temp = q.top(); q.pop();
        Ans+= temp.value;
        l=pre[temp.place];   r=nxt[temp.place];
        w[temp.place]=w[l]+w[r]-w[temp.place];
        change(l);    change(r);
        q.push((node){w[temp.place],temp.place});
    }
    printf("%d\n",Ans);
    return 0;
}
评论