Luogu1484种树|题解

Luogu1484种树|题解

十月 19, 2018

cyrcyr今天在种树,他在一条直线上挖了n个坑。这n个坑都可以种树,但为了保证每一棵树都有充足的养料,cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够,他至多会种k棵树。假设cyrcyr有某种神能力,能预知自己在某个坑种树的获利会是多少(可能为负),请你帮助他计算出他的最大获利。

n<=500000

很有趣的一道题

dp的做法我就不多赘述了.主要讲讲怎么$O(klogn)$实现它


首先我们考虑一个特殊情形:不限制树的数量上限,所有权值都为正数

假设$n=3$,用$01$串表示种树的情况的话,无非就是这两种:

  1. $010$
  2. $101$

假如目前策略是$010$的话,总价值$ans$为$val[2]$,如果满足条件:

$val[1]+val[3]>val[2]$

我们就可以改用策略$101$,此时价值增加量$f_1=val[1]+val[3]-val[2]$,种下的树的数量增加$1$

假设$n$大一些,例如$n=5$时,从$01010$转为$10101$的情形也大致一样:种下的树数量增加$1$,价值增加量为$f_2=val[1]+val[5]-f_1,(f_1含义见上一行,即01010的增加量)$

如果$f_2>0$,那么这个新的策略是值得的

于是我们发现了它重要的规律:这极其类似于求二分图匹配的增广路算法

也就是:路径上的$0$变为$1$,$1$变为$0$,种的树数量增加$1$

不过有一个区别:本题中进行一次类似”增广”的操作,会产生一个价值$f$,这个$f$可以通过容斥原理求得.

那么原题题意就明了了:我们的任务是进行不多于$k$次类似”增广”的操作,使得所有$f$之和最大


那么怎么实现这个操作呢?双向链表.

我们用一个节点来表示一段交错种树的坑的区间,初始状态下一个节点对应一个坑.

这个节点里要保存这段区间进行一次”增广”后产生的价值.初始状态就是原先这个坑的价值

如果进行了一次增广,那么区间就会和它左/右两边的区间合并,例如$0010100$,如果我们对区间$[3:5]$进行一次”增广”,那么就变成了$0101010$,区间扩大为$[2:6]$.这时候表示$[2:2]$的节点和表示$[6:6]$的节点都被$[2:6]$覆盖了,因此我们新建一个节点表示$[2:6]$,而原先的三个节点都打上删除标记.新节点直接与节点$[1:1]$和节点$[7:7]$相连.

由于我们要使$k$次”增广”的价值之和最大,显然把所有节点丢进一个大根堆里,按价值$f$从大到小取出就好了.


代码如下.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#define LL long long
using namespace std;
struct qwq{
        //the node in the Linked-list
        //it represents a sub-sequence of the array of holes
        LL val;//the value that the sequence can provide if we make it expand
        qwq *left,*right;
        bool if_del;//if the node has been deleted
        qwq (LL al,qwq *be):
                val(al),left(be),right(NULL),if_del(0){}
        qwq (LL al):
                val(al),left(NULL),right(NULL),if_del(0){}
};
struct pwp{
        //pointer to the node on the Linked-list
        qwq *p;
        bool operator < (const pwp &be)const{
                return p->val < be.p->val;
        }
};
priority_queue<pwp> h;
int main(){
        LL n,k;
        cin >> n >> k;
        LL al;qwq *be;
        scanf("%lld",&al);
        be = new qwq(al,NULL);
        h.push((pwp){be});
        for (LL i = 2;i <= n;++ i){
                scanf("%lld",&al);
                be->right = new qwq(al,be);
                be = be->right;
                h.push((pwp){be});
        }
        LL ans = 0;
        for (LL i = 1;i <= k;++ i){
                //take the node which owns the max value
                while(h.size() && h.top().p->if_del)
                        h.pop();
                qwq *p = h.top().p;
                h.pop();
                //we needen't to exactly chose k holes 
                if (p->val <= 0)
                        break;
                //make the sequence expand
                ans += p->val;//add value to the answer
                qwq *new_ = new qwq(0 - p->val);//create a new node to represent the larger sequence
                //the new node 's value is (left->val)+(right->val)-(origin->val)
                //if the left/right node exist
                //just like Augmenting-Path algorithm in gragh theory
                if (p->left != NULL){
                        //delete the left node,because it's sequence will be contained by the sequence of the new node
                        p->left->if_del = 1;
                        new_->val += p->left->val;
                        new_->left = p->left->left;
                        if (new_->left != NULL)
                                new_->left->right = new_;
                }
                else
                        new_->right = NULL;
                if (p->right != NULL){
                        p->right->if_del = 1;
                        new_->val += p->right->val;
                        new_->right = p->right->right;
                        if(new_->right != NULL)
                                new_->right->left = new_;
                }
                else
                        new_->right = NULL;
                //push the new node to the heap
                h.push((pwp){new_});
        }
        cout << ans;
        return 0;
}

文结.