poj 1949 Chores (拓扑排序+dp)

2017年11月8日 0 作者 CrazyKK

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

题意:

有n个任务,第i个任务需要时间xi来完成,并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。

给你任务信息,问你最短需要多少时间来完成任务。

思路:

拓扑排序+dp

拓扑排序的过程中做个dp,可以保证dp的顺序…

对于这道题,找出每条依赖链,然后做dp即可。