社区讨论
来教教我反悔贪心吧QAQ
P2949[USACO09OPEN] Work Scheduling G参与者 6已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @locvzt0u
- 此快照首次捕获于
- 2023/10/30 20:39 2 年前
- 此快照最后确认于
- 2023/11/05 07:08 2 年前
我死活证不出来这题的反悔贪心。。。虽然这题是最最基础的反悔贪心了。。
我理解的过程是:按 排序,然后使 递增,动态维护 的最优解。设选择物品的个数为 。当加入 时,若 ,则直接加入 (我可以理解)。若 ,则尝试将前面选择的一个物品扔掉,并加入 。
问题:有没有可能 的最优解不从 的最优解通过“反悔一次”得到,而是从某个次优解直接加入 得到?
回复
共 9 条回复,欢迎继续交流。
正在加载回复...