P3243 [HNOI2015]菜肴制作 题解

ppip · 2022-11-08 13:30:05 · 题解

最优解就是符合条件的排列中，反序列的字典序最大的排列。

这是最高赞题解的结论。然而，没人证明这玩意儿。

（本文仅提供证明。如何求字典序最大的请左转）。

定义两个拓扑序中更优的一个为“最小序”更小的拓扑序。

求证：一个 DAG 的拓扑序中“最小序”最小的的一个拓扑序，是反向字典序最大的一个。

证明：

首先，当 |V|=1 时结论显然。

其次，假设结论对于 |V|<n 均成立。设图 G=(V,E) 中最小点编号为 x，其中 |V|=n，则整个点集分为两部分：

• S=\{z\ |$ 存在一条路径 $z\to x\}
• T=V-S

特别地，有 x\in S。

Lemma 1：令 m:=|S|。则最小序最小的拓扑序 a 一定满足 \{a_x|1\leq x\leq m\} = S 且 a_m=x。

证明：由于 x 在拓扑序上的位置越小，最小序就越小，所以 x 尽可能靠前更优。由拓扑序的定义，S - \{x\} 中的所有点在拓扑序上一定排在 x 之前。

所以 a_p=x 是 p\geq m 的充分条件。于是最小的最小序满足 p=m。

现将整个图可以分成三个子图，其点集分别为 S-\{x\}、\{x\} 和 T。

由于 |S| + |T| = n，所以 |S-\{x\}|,|T| < n，由假设得其结论成立。

因为 x 是编号最小的，将 x 向后移不能获得更大的反向字典序。而 S-\{x\},T 的结论已证。于是对于图 G 结论成立。

所以对于任意的 DAG，由数学归纳法得结论均成立。

证毕。