Problem 1356 --算法实现题 3-1 独立任务最优调度问题（习题 3-3）

1356: 算法实现题 3-1 独立任务最优调度问题（习题 3-3）

上一题 正确率: $16.67\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $6$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划

Description

用 2 台处理机 A 和 B 处理 n 个作业。设第 i 个作业交给机器 A 处理时需要时间ai ，若由机器 B 来处理，则需要时间bi 。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai >= bi ，而对于某些 j,j≠i，有 a j < bj 。既不能将一个作业分开由 2 台机器处理，也没有一台机器能同时处理 2 个作业。设计一个动态规划算法，使得这 2 台机器处理完这 n 个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例：
(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。
算法设计：
对于给定的 2 台处理机 A 和 B 处理 n 个作业，找出一个最优调度方案，使 2 台机器处理完这 n 个作业的时间最短。

Input

输入的第 1 行是 1 个正整数 n, 表示要处理 n 个作业。接下来的 2 行中，每行有 n 个正整数，分别表示处理机 A 和 B 处理第 i 个作业需要的处理时间。

Output

将计算出的最短处理时间输出

Sample Input复制

6
2 5 7 10 5 2
3 8 4 11 3 4

Sample Output复制

15

推荐代码 查看1356 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$4 $ms] anonyuser 904350 2022-10-17 13:53:46
内存最少[$1240 $KB] anonyuser 904350 2022-10-17 13:53:46
第一AC anonyuser 904350 2022-10-17 13:53:46
第一挑战 张阳@网络工程152 176349 2017-12-14 00:41:18

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛