#P2224. [HNOI2001] 产品加工

    ID: 1240 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2001各省省选湖南背包

[HNOI2001] 产品加工

题目描述

某加工厂有 A、B 两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成。由于受到机器性能和产品特性的限制,不同的机器加工同一产品所需的时间会不同,若同时由两台机器共同进行加工,所完成任务又会不同。

某一天,加工厂接到 nn 个产品加工的任务,每个任务的工作量不尽一样。

你的任务就是:已知每个任务在 A 机器上加工所需的时间 t1t_1,B 机器上加工所需的时间 t2t_2 及由两台机器共同加工所需的时间 t3t_3,请你合理安排任务的调度顺序,使完成所有 nn 个任务的总时间最少。

输入格式

第一行为一个整数 nn

接下来 nn 行,每行三个非负整数 t1,t2,t3t_1,t_2,t_3,分别表示第 ii 个任务在 A 机器上加工、B 机器上加工、两台机器共同加工所需要的时间。如果所给的时间 t1t_1t2t_200 表示任务不能在该台机器上加工,如果 t3t_300 表示任务不能同时由两台机器加工。

输出格式

仅一行一个整数,表示完成所有 nn 个任务的最少总时间。

5                            
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1
9

提示

对于所有数据,有 1n6×1031\le n\le 6\times 10^30t1,t2,t350\le t_1,t_2,t_3\le 5