反悔自动机与反悔堆——有关贪心的反悔操作

其实两个东西都是堆。区别只不过一个是利用差值等巧妙设计等效权值，另一个则单纯进行判断。

 

反悔自动机

（名字是我自己起的）

贪心是不能反悔的。因为它就是选择当前的最优解。

但是如果当前最优解不是全局最优解怎么办？

我们可以设计一种反悔的方法，并且和贪心的手法结合。

使得贪心随便选择，都可以达到正解。

姑且叫反悔自动机。

 

基本的设计思路是：

每次选择当前直观上最接近最优解的方案。

但是发现不对。不是最优子结构

然后想办法怎么支持自动反悔。

 

0.边有边权，树上选择k个边不相交的路径，总和最大（权值有正有负）

求k次树的直径，每次把直径上的边权取反即可

 

1.经典问题：CF865D Buy Low Sell High

每次用最小的买入，等到一个可以赚钱的天就卖出。

不对是因为：可能这个买入的股票要等到后面更贵的那一天再卖出。

 

利用做差，C-A=B-A+C-B，等效转化

用最小的买最大的，然后把差值计入答案，把B放进去两次，再取B为最小的时候，C-B的差值计入ans，相当于用A买入以C卖出

相当于B没有用，所以额外再加入一次B，以防后面需要用B买入再D卖出。

 

2.类似的：

BZOJ 2151
• 有一个长度为n的环，选择m个两两不相邻的位置。
• 每个位置都有一个价值Vi，如果选择这个位置就可以得到Vi的价
值。
• 求最大的价值总和，或输出无解。

直观来看，每次选择能选择的最大的价值。

为什么不对？因为可能选择了这个最大的，邻居就不能选择。例如1,5,6,5选择了6，就只能再选择1，不如5,5

而且，这个贪心的错误的点就是这里。对于最优解位于其他的位置上的情况，这种贪心都是成立的。

 

考虑怎么支持反悔。

还是利用差值。

用双向链表维护相邻的关系。用堆维护所有权值的最大值。

选择了A，把W[L[A]+W[R[A]-W[A]建成一个新的点P，令这个P的L，R分别是：L[L[A]],R[R[A]]，然后删掉L[A],R[A]，

每次取最大值即可。

因为，如果有a,b,c,d,（紧挨着就是相邻），并且a+c>b+d,那么，就有a+c-b>d

所以，即使我们先选择了b，但是由于a+c-b>d，我们会接着选择a+c-b，就相当于选择a+c

 

 

 

 

反悔堆：

（名字也是我自己起的）（其实就是一个堆）

这个不是无脑地随便贪心了。因为没有什么等效权值的替换。

其实思路差不多。

我们还是按照一个贪心策略贪心，然后找出来不足。

想办法反悔。

和反悔自动机不同的是，这个要人工反悔。

例题：

[JSOI2007]建筑抢修——贪心反悔堆