基于允许非法状态的贪心策略
在做题目的过程中，我们会发现一种奇特的解法，以二分法求最长上升子序列 \(\text{LIS}\) 为例。
此时我们需要先记录一个长度为 \(len\) 的 \(b\) 数组记录当前的最长上升子序列，然后再用 先看过程
- 如果当前 \(a_i > b_{len}\) 那么添加一位，增加答案。
- 如果以上不成立，那么选择第一个大于 \(a_i\) 的位置 \(j\)，将 \(b_j\) 替换为 \(a_i\) 。
那么显而易见，第二重情况是 非法 的，即当前的数列并非一个子序列。
但这的确是正确的，于是我们可以分析它的
正确性
首先考虑对于答案的影响，注意到此时操作为 替换 ，对答案是恰好抵消，因此确实长度正确。
不劣性
如果以此操作继续下去，用基本功可以发现再当前我们可以在 \(a_i<a_k<b_j +1\) 时，将 \(a_k\) 弄进来。但若 \(a_k < b_j\) 的话就不可以，因此此时我们的 加入门槛 就降低了。于是依照此方案不断添加，若没有到达 \(1\) 操作答案不变，正确性保证。同时若到达了答案更新，不难发现此时 合法 !
因此简单总结一下几条性质。
- 采用非法状态时答案正确，或者说一定存在这样的答案，只不过并非这样的状态。
- 这个策略会使得答案更优，且影响答案时已然合法。
然后我们可以看下在反悔贪心的应用。
反悔原题
这题多数人都给出了多次反悔的想法，我的思路大体上为能做就做，不能做就看是否能更优这样的一次反悔。
但是有一个重要的雷点就在于其实我们并不需要判断反悔时是否时间充足。
注意到反悔时对答案不影响，然后能做时特判是否时间充足即可。
这个与上一个是十分类似的。
(未完待续)