A Communicate Topological Order
很玄幻的一题。
可以是认为是结论？但是看了结论肯定没有用啊。要知道怎么想出来的啊。想不出来。唉。
首先，考虑什么情况下 Aoki 可以推断出来这个排列。
因为 Aoki 是知道这个图长什么样的。而他能利用的只有大小关系。
Takahashi 给他填的数中，能帮助他：
- 确定更多的大小关系。
- 占掉一个空位。
先说一下我的一个错误思路：找到图 \(G\) 的最长路然后输出。（\(p\) 都没用上怎么可能对）
这里只用到了上面的一个方面：拿已知数占掉空位。
Try to come up with an better strategy.
尝试将图上的点分成若干个集合。
通过告诉 Aoki 每个集合 \(S\) 中的 \(|S|-1\) 个元素，然后可以使 Aoki 确定剩下的一个元素。
但是也不能乱分。如果集合之间没有连边，那么即使 Aoki 确定了么每个点集之间的偏序关系，他也不能确定点集之间的偏序关系。
这样处理优在哪里呢。首先一定不劣于上面的最长链法。
考虑这个例子：
只需要告诉 Aoki \(p_3 = 2\) 即可。
分集合的话，可以考虑分成 \(\{2\}, \{1,3\}, \{4\}\)。
然后发现每个集合的值域是一个连续段。（？？？？？？how to find it）
然后就可以写出一个 DAG 的 DP。定义 \(f_i\) 表示把 \([1, i]\) 中的值能最多分成多少个集合。
然后相邻两个集合之间是要有连边的。转移大概就是
\[f_i = \left\{
\begin{matrix}
f_{i-1}+1& 存在 j 使得图上j的点到i的点有边\\
f_{i-1} &\text{otherwise.}
\end{matrix} \right.
\]
答案是 \(n-f_n\)。证明可以看官解。