社区讨论

来教教我反悔贪心吧QAQ

P2949[USACO09OPEN] Work Scheduling G参与者 6已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@locvzt0u
此快照首次捕获于
2023/10/30 20:39
2 年前
此快照最后确认于
2023/11/05 07:08
2 年前
查看原帖
我死活证不出来这题的反悔贪心。。。虽然这题是最最基础的反悔贪心了。。
我理解的过程是:按 tt 排序,然后使 ii 递增,动态维护 1i1\sim i 的最优解。设选择物品的个数为 jj。当加入 i+1i+1 时,若 j<tij<t_i,则直接加入 ii(我可以理解)。若 j=tij=t_i,则尝试将前面选择的一个物品扔掉,并加入 ii
问题:有没有可能 1i+11\sim i+1 的最优解不从 1i1\sim i 的最优解通过“反悔一次”得到,而是从某个次优解直接加入 i+1i+1 得到?

回复

9 条回复,欢迎继续交流。

正在加载回复...