本题之前一直没有细想...

Problem

cyrcyr 今天在种树，他在一条直线上挖了 n 个坑。这 n 个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr 不会在相邻的两个坑中种树。而且由于 cyrcyr 的树种不够，他至多会种 k 棵树。假设 cyrcyr 有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

Solution

题解见 luogu。
现在问题就是为什么一定是反悔为 $a_{i-1}+a_{i+1}$ 的情况，而不是其它。
我觉得相对容易理解的的证法如下。

a1 a2 a3 a4

我们选了 a2.
若要反悔，应当反悔选择 a1 a3.
我们假设反悔选择 a1 a4 更优。
则有 a1+a4>a1+a3，因此 a4>a3
也有 a1+a4>a2+a4（这是肯定的，否则就不会反悔），因此 a1>a2.
a1 和 a4 在堆中的顺序优于 a2,a3，因此 a1,a4 优先考虑，a2 反而变成了反悔的对象，这与命题矛盾。

如果加个 a5？
那我们反悔 a2，再选 a5，是可行的，处于考虑范围之内。
如果加个 a6？
那它可以分解成 a1+a4+a6 或 a1+a3+a6。而反悔为 a1+a4/a1+a3 已纳入考虑范围之内。

以此类推易证，所有情况皆已被我们包含（严谨的方法可以再用数学归纳法简单证明）。
所以我们反悔时肯定选择 a1,a3，是肯定的。

那么加入反悔操作的正确性？贪心为什么能得到最优解？

我想大概是正确的贪心顺序把贪心的后效性给去除了吧（使贪心具有阶段性决策最优性）。像网络流，又不完全一样。

如果你变成乱搞合并，你不但得不到最优解，你一定选择两边的策略也是错的。

这是一个贪心顺序与证明紧密结合的题目。

合并的话，显然把反悔方案也合并了。妙的是，选择反悔操作不需要回溯，因为反悔之后现在的状态就变成了你应该得到的状态。

比如你选择 a2,a4，你合并了 a1,a3,a5.
然后你选择反悔，变成选择 a1,a3,a5，然后把 a0,a6 合并。
你相当于在阶段性中选择了最优解，把所有的反悔操作变成了物件。

这好像又回到贪心的概念了？

果然这种题还是不该深究...

本文链接：https://pst.iorinn.moe/archives/tree.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆