cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。
n<=500000
很有趣的一道题
dp的做法我就不多赘述了.主要讲讲怎么$O(klogn)$实现它
首先我们考虑一个特殊情形:不限制树的数量上限,所有权值都为正数
假设$n=3$,用$01$串表示种树的情况的话,无非就是这两种:
- $010$
- $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;
}文结.
