poj 3249 Test for Job (拓扑排序+dp)

http://poj.org/problem?id=3249

题意:

给一个DAG,现要从一条入度为0的点到一个出度为0的点,问最大点权和。

思路:

其实比较容易想到搜…不过复杂度会炸?

由于到一个点的最大点权和,需要更新完所有到达它的路线之后才能确定。

容易联想到拓扑排序,我们可以在拓扑排序的同时做dp

dp[v] = max(dp[v],dp[u]+a[v]),初始化对于入度为0的点,dp[i] = val[i].

其实拓扑+dp是一种比较一般化的套路…?

因为拓扑保证了更新顺序

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz