题意:给一个\(dag\),每一个点有一个访问时间。
现在可以同时访问两个点,但当连向这个点的所有点都被访问完成后才可以访问这个点。
问最短访问时间。
思路:一眼贪心。可惜是错的。
第二眼暴搜。就这么办。
搜索的状态很普通,现在在第\(i\)秒,访问着\(a\)和\(b\)两个点。
那么每次把他们的时间减一,并且如果他们访问完成了就枚举换到另一个点。
可惜这样肯定会TLE,那么最优化剪枝:
如果当前的所有时间分成两部分,它们的和之\(max\)最小,那么这就是从现在到结束的最短时间。
这个可以用\(dp\)很容易地求出来。
所以判断一下当前时间加上这个时间大于不大于答案即可。
写的细节比较多??我捣鼓了半天。