acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
登录
注册
题目详情提交记录(0)
  • 随机化大法好啊

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

    userId_undefined

    Gragher

    题解仙人尊贵铂金传道者CSP-J一等奖出题人代码纠察员
    22阅读
    5回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页