1421-机器零件加工


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:2 难度:4


题目描述:

n个机器零件{J1J2Jn},每个零件必须先由机器1处理,再由机器2处理。零件Ji需要机器1、机器2的处理时间为t1it2i。如何安排零件加工顺序使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成所需的总加工时间最短?


输入描述:

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入机器零件个数n(1<=n<=20)。
接下来有n行,每行输入两个数,代表第一台机器上的加工时间和第二台机器上的加工时间t1i、t2i(1<=t1i、t2i<=100)。

输出描述:

对于每一组输入,输出最短机器零件加工时间。
每组的输出占一行。

样例输入:

2
6
5 7
1 2
8 2
5 4
3 7
4 4
7
3 7
8 2
10 6
12 18
6 3
9 10
15 4

样例输出:

28
65

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!