这题是不是可以用拓扑排序求最长路

P1434 [SHOI2002] 滑雪

lzyqwq @ 2022-05-28 10:44:05

每个点编号为 m(i-1)+j，向四周比自己低的节点建边（i=1 或 j=1 时判断边界），然后建成了一个 DAG，就可以跑拓扑了！

by lzyqwq @ 2022-05-28 10:44:21

求验证

by SunSkydp @ 2022-05-28 10:52:05

@蒟蒻·廖子阳可以（即答

by lzyqwq @ 2022-05-28 10:52:34

@SunSkydp .

by Z_301 @ 2022-05-28 11:01:42

其实这题就是DAG求最长链，拓扑dp和dfs dp是本质相同的吧

by UnyieldingTrilobite @ 2022-05-28 11:18:28

@蒟蒻·廖子阳本质上如果你考虑 dfs 做拓扑排序的话你会发现没有区别

by lzyqwq @ 2022-05-28 11:33:22

@UnyieldingTrilobite @Z_301 感激不尽