最近做到了两道题，有同一种思想方法，我称之为“反悔贪心”
先放我的两只题解
LuoGu3620： [APIO/CTSC 2007]数据备份
LuoGu4597：序列sequence
到底什么是反悔贪心呢，首先是贪心，然而贪心并不是最优的，我们这是需要增添一个反悔机制来进行优化这个贪心
比如我放的第一题，贪心策略就是每次取最小的，但是可能不是最优的，所以引入反悔贪心，把某个值 A A A取出后，加入 B − A + C B-A+C B−A+C，意在反悔时可以用 B , C B,C B,C替代 A A A
我放的第二题，也可以说成反悔贪心，策略是每次把我前面那个值减小成当前值，但是可能不合理，或答案可能比最优值还要优，那么加入反悔机制，这里的反悔机制，就是把前面的最大值改成当前值，意在巧妙利用题目本身的诸多性质，自动调整数的大小
那么如果有的题目，暴力已经无法继续优化，并且有一个
n
a
i
v
e
naive
naive的贪心的时候，这时不妨大胆的去想一想反悔贪心可不可以
这个反悔贪心的思维真的是非常的有趣
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
