【学习笔记】反悔贪心

69 阅读 0 评论 46 点赞

我是靠谱客的博主诚心往事，最近开发中收集的这篇文章主要介绍【学习笔记】反悔贪心，觉得挺不错的，现在分享给大家，希望可以做个参考。

最近做到了两道题，有同一种思想方法，我称之为“反悔贪心”
先放我的两只题解
LuoGu3620： [APIO/CTSC 2007]数据备份
LuoGu4597：序列sequence

到底什么是反悔贪心呢，首先是贪心，然而贪心并不是最优的，我们这是需要增添一个反悔机制来进行优化这个贪心

比如我放的第一题，贪心策略就是每次取最小的，但是可能不是最优的，所以引入反悔贪心，把某个值 $A$ 取出后，加入 $B - A + C$ ，意在反悔时可以用 $B, C$ 替代 $A$

我放的第二题，也可以说成反悔贪心，策略是每次把我前面那个值减小成当前值，但是可能不合理，或答案可能比最优值还要优，那么加入反悔机制，这里的反悔机制，就是把前面的最大值改成当前值，意在巧妙利用题目本身的诸多性质，自动调整数的大小

那么如果有的题目，暴力已经无法继续优化，并且有一个 $n a i v e$ 的贪心的时候，这时不妨大胆的去想一想反悔贪心可不可以
这个反悔贪心的思维真的是非常的有趣

以上就是诚心往事为你收集整理的【学习笔记】反悔贪心的全部内容，希望文章能够帮你解决【学习笔记】反悔贪心所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。