[HEOI 2013 day2] SAO (树形动态规划)

题目大意

给一棵N个节点的有向树(N <= 1000),求其拓扑序列个数。

思路

我们将任意一个点作为根,用dp[i][j]表示以节点i为根的子树满足节点i在第j个位置上的拓扑序列的个数。在求节点cur的状态的答案时,我们需要枚举cur的所有儿子i,通过组合数计算将i子树的序列中i前面的部分与目前cur的序列中cur之前的部分合并的方案数,当然后面的部分也要算。

我们不妨假设当前访问的儿子i需要早于cur在序列中出现,用cnt[i]记录以i为根的子树的大小,由于i早于cur,在i序列中早于i的也必须早于cur,故可以得到

[HEOI 2013 day2] SAO (树形动态规划)

如果儿子i需要晚于cur也是类似的

[HEOI 2013 day2] SAO (树形动态规划)

上一篇:LeetCode: Sort Color


下一篇:[0] 四色原型