2023.04.26-实习-第一题-引擎模块初始化 - Problem Detail - CodeFun2000

ID: 258

1000ms

256MiB

Difficulty: 5

No testdata at current.

思路：拓扑排序

解法1:DAG上的最长路

根据题目意思以及样例，我们可以发现实际上就是给我们一张有向无环图。问DAG上的最长路径。我们可以使用拓扑排序+动态规划求解。

要求最长路径，我们定义 $dp[i]$ 为从任意起点到点 $i$ 的最长路径长度，那么转移为:

dp_i = max(dp_j) + 1 , j \in pre(i)