LP1484 种树 [未充分证明]

Author Avatar
空気浮遊 2018年06月14日
  • 在其它设备中阅读本文章
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

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

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 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material