算法基础贪心本页总览贪心概述参考资料 贪心 - OI Wiki 贪心算法 - 维基百科，自由的百科全书 贪心 贪心算法（Greedy Algorithm）是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。 可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。 反悔贪心 反悔贪心的思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。 例题 题面code洛谷 P1209 [USACO1.3] 修理牛棚 Barn Repair一行 sss 个牛棚，其中 ccc 个有牛。用至多 mmm 块木板（每块覆盖一段连续牛棚）盖住所有有牛的牛棚，求最小木板总长度。 题面code洛谷 P1792 [国家集训队] 种树环形排列 nnn 个位置，第 iii 个美观度为 AiA_iAi，相邻两位置（含 111 与 nnn）不能同时种树。恰好种 mmm 棵，求最大美观度之和；无法种满则输出无解信息。