求教复杂度问题

回复帖子

@soul_M 2018-08-23 09:22 回复

虽然A了但是不太清楚之前会T。

自己想的思路:找到所有入度为0的root,对于每个root向下dfs,如果子节点答案小于父节点加一,就更新并由该子节点继续向下dfs;否则就不管该子节点。

题解思路:对于每一个点i,反向dp,通过父节点更新子节点答案,如果父节点已经有答案,那么显然是最优,此时子节点答案就为父节点加一;如果父节点也没有被更新过,就由父节点继续向上dp。

感觉两种复杂度都是对的啊......为什么法1过不了最后一个点呢?

求教 @BLUESKY007 @dreagonm @maomao9173 @风浔凌 @dummyummy @__stdcall

@__stdcall 2018-09-02 12:55 回复

简化题意:

给一个dag,求以每个点结尾的最长路长度。

所以说随便dp一下就没了。

法1其实是dfs版的spfa。。。复杂度指数级的,当然要t啊