LP1484 种树 [未充分证明]

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

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://acxblog.site/archives/tree.html
本文采用 CC BY-NC-SA 3.0 协议进行许可