关于题解中那篇依赖关系dp,为什么求的是后序遍历而非先序遍历?

P1064 [NOIP2006 提高组] 金明的预算方案

HL69 @ 2021-08-16 17:13:06

如果理解没错的话,那篇题解的意思应该是:把依赖关系转化为树形图之后,求它的拓扑排序,转化为线性dp。

按照题目的意思,应该是先选取主件才能选取附件,那么一个点的父节点(父节点代表依赖的主件)不应该在线性dp序列的前方吗,不应该求的是先序遍历吗?

对此十分疑惑,希望各位前辈们指点一下。


|