【Topcoder 1879】Scheduling

题意:给一个\(dag\),每一个点有一个访问时间。

现在可以同时访问两个点,但当连向这个点的所有点都被访问完成后才可以访问这个点。

问最短访问时间。

思路:一眼贪心。可惜是错的。

第二眼暴搜。就这么办。

搜索的状态很普通,现在在第\(i\)秒,访问着\(a\)和\(b\)两个点。

那么每次把他们的时间减一,并且如果他们访问完成了就枚举换到另一个点。

可惜这样肯定会TLE,那么最优化剪枝:

如果当前的所有时间分成两部分,它们的和之\(max\)最小,那么这就是从现在到结束的最短时间。

这个可以用\(dp\)很容易地求出来。

所以判断一下当前时间加上这个时间大于不大于答案即可。

写的细节比较多??我捣鼓了半天。

上一篇:[Python] csv模块用法小结


下一篇:绿色调度研究方向