菜肴制作贪心的证明

菜肴制作贪心的证明

[HNOI2015]菜肴制作贪心的证明

先吐槽一句为什么网上都没人证这个东西,我觉得一点也不显然啊。。。

判环不用说了,现在处理一个DAG。考虑按题意模拟:建反图(边从后选的点连向先选的点),每次找全局最小的点,并把候选集合缩小为这个点在图上的所有后继,再在当前候选集合中选择最小的点并把候选集合更新为它的后继,不断重复此过程直至候选集合只有一个点,就把这个点从图上删除并放到答案序列的末尾。这种做法最后得到的答案序列的正确性是显然的。

观察一下数据范围,发现直接模拟不太能做。考虑每次选了全局最小点,这个点和它的后继在答案序列上一定会占据一段前缀,并且这个点一定在这段前缀的最后一个位置,因此把这些点在图上删掉并不会影响其它点的决策,而且处理这个点的后继就是一个子问题。我们每次都取当前的全局最小点并把它和它的后继在图上删除,最后删掉的点一定是当前没有入度的最大的点,这个点一定会被放在答案序列的末尾,如果把这个点删除,剩下的所有点又成为了一个子问题。这样我们就得到了正确的决策:每次取当前没有入度的最大的点删除并放到答案序列的末尾。实际上就是到处说的拿大根堆拓扑排序的拓扑反序。

05-11 15:14