ZAFU ACM

Appearance

贪心 ​

贪心算法，是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，只有在特定的问题下，贪心法才能获得最优解。因此使用贪心法时，要确保自己能证明其正确性。

贪心算法常见的有两种证明方法：

  1. 反证法：交换两个元素后答案不会更好，那么可以确定当前的算法是最优解了。
  2. 归纳法：通过归纳证明答案是最优解。

P4995 跳跳！ ​

给定石头的高度 h，从第 i 块石头跳到第 j 块上耗费体力 (hi−hj)2，求最耗体力的路径。

凭借一些数学的灵感，可以猜到是在剩余的石头中，高度差当前最大的来回跳。即“大小大小”这样反复横跳。

如何证明呢？假设 hi 已经是要跳的序列。展开求和式

S=∑k=1n−1(hk−hk+1)2=∑k=1nhk2−2∑k=1n−1hkhk+1

注意到平方和为一个定值，重点在后半式。记 Hk=hk+1，有

∑k=1n−1hkHk

利用高中时学的排序不等式，有

反序和⩽乱序和⩽顺序和

直接有反序最小。

参考资料 ​

练习 ​