贪心是一种常用的算法，它能够获得局部最优解，但我们往往需要的是全局最优解，所以我们在贪心的时候加入和反悔的机制，让他能够得到全局最优解。
由于网络流中的退流操作本质上也是反悔贪心，所以在实现反悔贪心时类似费用流的，也会被成为模拟费用流。
一般的实现时在贪心之后加入一个和贪心值相反的值或重构问题使得变成原问题等方式实现。
CF865D Buy Low Sell High
这个问题也叫老鼠进洞问题。
我们考虑到达第 \(i\) 天的时候，我们找到前面几天中最小的买入价格 \(a_j\) ，它会对答案做出 \(a_i-a_j\) 的贡献。
但由于一天只能买入一张或者卖出一张，在类似 1 2 100 的结构中贪心就时错误的。
不难发现，如果 \(i\) 会选定 \(j\) 和它做贡献，则在全局最优解中， \(a_j\) 也一定会做贡献。
令 \(a_j\) 与 \(a_k\) 做出 \(a_k-a_j\) 的贡献（ \(j<i<k\) ） 。由于 \(a_k-a_j=a_k-a_i+a_i-a_j\) 。
右式的后两项就是我们贪心的结果，这也就意味着，如果我们再在后面贪心的取一次 \(a_k-a_i\) 即可。
题目有每个数只能买入或卖出一次的限制，所以我们只要在贪心取数的时候额外加入一个 \(a_i\) 即可。
使用小根堆维护最优解，最终复杂度为 \(O(n\log n)\) 。
Luogu P1484 种树
因为不能选择相邻的数，所以在取了最大值 \(a_i\) 的时候， \(a_{i+1}\) 和 \(a_{i-1}\) 就不能选了，但可能全局最优解应该是 \(a_{i+1}+a_{i-1}\) 的。
例如在 \(n=5,k=2\) 时，数据 1 99 100 99 1 可以卡掉纯贪心。
考虑 \(a_{i+1}+a_{i-1}=a_{i}+(a_{i+1}+a_{i-1}-a_{i})\) ，比我们的贪心值多了一个 \(a_{i+1}+a_{i-1}-a_{i}\) 。
但它同时也去多取了一个数，所以考虑 \(a_{i-1} a_i a_{i+1}\) 三个数在取了 \(a_i\) 后替换成 \(a_{i+1}+a_{i-1}-a_{i}\) 这一个数。
发现这样不影响限制，维护双线链表和大根堆即可。
集训队互测 Round1 Astra 1 Birth
不难证明最优答案必然把答案划分成若干个连续的 \(00\dots0\) 或 \(11\dots1\) 。
在分割段数减少的时候，我们需要删去一些连续段来使得损失最小。
我们会发现三个性质：
- 删去边上的串可以减少一次分割，删去中间的串可以减少一次分割。
- 删去相邻的两端一定不优。
- 可以保留一个形如 \(0\dots 01\dots 1\) 的结构。
所以我们需要求的就是看有多少个不相邻的连续段在最终答案中不做贡献，先枚举两端的段取不取，在考虑中间的。
这就变成了类似上一题的做法，负责都为 \(O(n\log n)\) 。
在段数小于 \(3\) 的时候不一定有 \(0\dots 01\dots 1\) 结构，所以需要特判，可以在 \(O(n)\) 的复杂度完成。
CF280D k-Maximum Subsequence Sum
比较经典的 GSS 问题，每次找到区间最大的子段，其对答案做出贡献，然后将区间内的所有值取反。
用线段树维护区间和\最大前缀\最大后缀\最大子区间，复杂度为 \(O(n\log n+m\log n)\) 。