关于反悔贪心一些题的大概思路

反悔贪心是一种贪心的改进，如果后面你后悔了还可以撤销以前的操作。所以叫反悔贪心。

后面有几道例题，就用这些题来了解反悔贪心算法。

P2949

可以将所有工作按照 deadline 来排序，然后来从左往右扫贪心选。

首先能选的肯定选对吧，因为这样你的收益就会变多。然后选到后面你会发现你的总的工作时间已经大于了这个工作的 deadline，因为每一项工作只需单位时间，所以就可以舍弃前面的不比这项工作值的一项工作来做这个工作。这样虽然你的工作总数不变，但是你的钱变多了。这是好的。

我们可以用小根堆来维护之前做的工作的利润。

你扫到这个工作并且可以做这项工作时，那就选，这肯定是好的。然后把利润 push 到堆里。
否则你扫到这个工作并且你现在的工作总时间已经大于这个工作的 deadline 时，如果这个工作的利润大于堆顶的利润，那么就把总收益减去堆顶然后再加上现在这个工作的利润。pop 堆顶，并把这个工作的利润 push 到堆里。

最后输出总收益即可

这道题也用与上一道题类似的思想：

按照报废时间给这些建筑排序，然后再从左往右扫。

建立一个大根堆，维护之前已经修理完毕的建筑的修理时间。

如果这个建筑你能修，那么就修，这肯定是好的。把修理时间 push 到堆里，然后答案。
如果这个建筑你不能修，那么如果他的修理时间小于堆顶的修理时间，那么就说明可以用这个建筑来替换之前的一个不优的建筑。答案不变但是可以缩短修理时间。可以证明舍弃堆顶优化是最大的，这也是好的。把总修理时间减去堆顶再加上现在的建筑的修理时间，pop 堆顶，再将这个修理时间 push 到堆里面。

看清楚题面！！！你有个单位时间是不用再走回点的！！！！我就因为这个被硬控了好久……

这道题的思路也是反悔贪心，和前面的相似。维护一个大根堆，先把所有的点按照坐标排序，然后从左往右贪心：

但是你在第二个操作了之后会很明显的感觉到有些情况答案会变小。所以我们要新增一个总答案，扫到每一个点时让他和当前答案取。最后输出总答案即可。

首先想朴素 DP 做法：

设为「考虑区间」为，种下了棵树的最大获利。

那么 DP式就是：

$dp_{i, k} = \max(dp_{i-1, k}, dp_{i-2 ,k-1} + val_i)$

max 里的第一项就是不选的获利，第二项是选的获利（因为不能相邻所以只能选）。

时间复杂度，可以获得分的 hào 成绩。

考虑优化。

你第一眼看到这题肯定会想到贪心，然后手玩了一下发现是假的。因为题目中要求不能让这两棵树相邻。

现在我们该考虑的是怎么把这个假的贪心变成真的。

你回到原本的那个贪心。如果你想选这个点，那么你旁边的那两个点就不能选。如果你选到一半，然后又后悔了，又想选那两个点，那又该怎么办？

我们可以想到一个 trick：如果你选了这个点，那么你就可以把他左右的那两个点和删掉，然后将点的权值变为，这样你想反悔了，那就重新选这个点，就可以削除之前选的影响，转为选和了。

但是要注意：如果你选了这个点，那你左右两边的点就不能选。我们可以记一个数组，选一个点时就把他左边的点和右边的点的值记为，就不能选。然后再更新：

我们把所有选的点的值和编号 push 进一个大根堆里，想选的时候就选堆头。然后再 push 一个处理了之后的点进去。如果已经选了个点又或是堆头的值已经小于等于，那就不选了，直接输出当前答案。

思路和上一道题一模一样，但是需要改一个地方：

，。

题目要求有个点，取出任意的个点让他们配为对，让这对的每一对的两个点之间的距离之和最小。

我们转化一下题意，把每两个点之间的距离抽象成一个点，这样就有了，这样就变为了：

有个点，取出个点使这个点两两不相邻。求这个点最小的权值和。

发现了什么，这个跟上面的两道题都很像！

于是就用上面两道题的思路来做。但是因为和上面的不一样，是求最小值。所以我们要设第个抽象点和第个抽象点的权值改为。这样才能避免对答案造成的影响。