题解：P1484 种树

· · 题解

upd:

题面

本题除了思维的难度大了一点之外，还是很简单的，方法与 [国家集训队]种树 类似，通过链表维护区间，优先队列求最值就可以了。但还是有一些细节。

我们设 nxt_i 表示链表中编号为 i 的元素的下一个元素的编号，per_i 表示链表中编号为 i 的元素的上一个元素的编号，a_i 表示链表中编号为 i 的元素的值。

当我们从优先队列中取出一个值时，把它累加进答案后，就表示我们选了这棵树。那么它两边的树就都不能选了。但是，有可能选两边会更优。

这时，代码的精髓就来了：“后悔处理”。如果现在我们选了 i，那我们就可以 a_i 变为 a_{per_i}+a_{nxt_i}-a_i。不难发现，如果我们选了这个新的 i 那么就相当于我们选了 per_i 和 nxt_i，而没选 i。

另外，还有一个细节是我们可以不种到 m 棵树，所以我们需要一边处理，一边求答案的最大值。

代码

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  int n,m,ans,cnt,a[500005];
  int l[500005],nxt[500005],per[500005];//数组模拟链表
  struct node{
      int a,x;
      node(){}
      node(int c,int d){a=c,x=d;}
      bool operator<(const node &t)const{
          return a<t.a;
      }
  };//结构体存储节点信息
  priority_queue<node>q;
  bool vis[500005];
  signed main()
  {
      scanf("%lld%lld",&n,&m);
      for(int i=1;i<=n;i++)scanf("%lld",&a[i]),q.push(node(a[i],i));
      for(int i=1;i<=n;i++)nxt[i]=i+1,per[i]=i-1,l[i]=a[i];
      while(m--){
          while(vis[q.top().x])q.pop();//弹出已经不存在的
          node tmp=q.top();
          q.pop();
          vis[nxt[tmp.x]]=vis[per[tmp.x]]=1;//标记
          ans+=tmp.a;//累加
          tmp.a=-tmp.a+l[nxt[tmp.x]]+l[per[tmp.x]];
          l[tmp.x]=tmp.a;
          per[nxt[nxt[tmp.x]]]=tmp.x;
          nxt[tmp.x]=nxt[nxt[tmp.x]];
          nxt[per[per[tmp.x]]]=tmp.x;
          per[tmp.x]=per[per[tmp.x]];//删去左右两边的节点
          q.push(tmp);//因为可以不种m棵树，所以要一边维护一边更新答案
          cnt=max(cnt,ans);
      }
      printf("%lld",cnt);
      return 0;
  }