回 帖 发 新 帖 刷新版面

主题:[讨论]动态规划题<我想了好多天了><高手进,初学者就别浪费时间了>

有两台机器a,b;有n个任务,对每个任务,可在a或b中的任一台上完成,且只能在一台上完成;
已知对第i个任务,其在a,b上运行所需时间分别为A[i],B[i],(一般情况下A[i]<>B[i])
求一种方案使时间最短(时间=任一台机器开始时间 到 最后一台机器结束时间)
样例输入:
n{任务个数}
n个integer{各任务在a上的运行时间}
n个integer{各任务在b上的运行时间}
样例输出:t{任务全部完成的最短时间}
样例输入
3
1 2 1
3 2 3
样例输出 
2
{一种可行的方案为:在a上处理任务1,3;
                  在b上处理任务2}
时间=max{a的运行时间,b的运行时间};
******如果有别的算法也可(枚举除外)******

回复列表 (共13个回复)

11 楼


累啊,遍了1小时,[em1][em1]..............
    耐性看完.....

12 楼


对不起,参加完信息竞赛我就把这事忘了

上边的那道题用动归,别的方法的正确性没有证明

13 楼

晕,我这样的菜鸟不小心就进来了。。。
不过我至少知道这是算法导论上的例题。。。
菜鸟立即闪人

我来回复

您尚未登录,请登录后再回复。点此登录或注册