还是随机大法好啊,状压 DP 还是太吃操作了。
题目分析
容易发现对于所有 1,21,21,2 类任务先执行 A 还是 B 都是唯一的,但是对于 333 类任务是需要决策的。显然没有贪心策略(可能有但是笔者太菜想不到)决定 333 类任务是现在机器 A 上执行还是机器 B 上执行,那就直接“随机代替思考”。
确定每个任务先做 A 还是 B 之后还需要每个任务之间的顺序。同样“随机代替思考”,直接随出来一个 nnn 的全排列。
得到所有任务执行顺序之后还需要算出当前状态下的最小总时间。这个是好求的,这里不细说,读者自行思考。
其实上述策略已经是一个完整的解题步骤了,不过还可以继续优化,也就是一个在随机化题目中非常常见的优化策略“局部搜索”,在当前得到的较优解附近进行搜索。虽然已经不能保证搜到最优解,但一定会比常规做法更快搜到最优解。
CODE