#4004. usaco-4.2.3 工序安排
usaco-4.2.3 工序安排
题目描述
一家工厂的流水线正在生产一种产品,这需要两种操作:操作 A 和操作 B.每个操作只有一些机器能够完成.
上图显示了按照下述方式工作的流水线的组织形式.A 型机器从输入库接受工件,对其施加操作 A, 得到的中间产品存放在缓冲库.B 型机器从缓冲库接受中间产品,对其施加操作 B,得到的最终产品存放在输出库.所有的机器平行并且独立地工作,每个库的容量没有限制.每台机器的工作效率可能不同,一台机器完成一次操作需要一定的时间.
给出每台机器完成一次操作的时间,计算完成 A操作的时间总和的最小值,和完成 B操作的时间总和的最小值.
INPUT FORMAT
第一行 三个用空格分开的整数:
- ◇N,工件数量 (1<=N<=1000).
- ◇M1,A 型机器的数量 (1<=M1<=30).
- ◇M2,B 型机器的数量 (1<=M2<=30).
第二行…等 M1 个整数(表示 A 型机器完成一次操作的时间,1..20),接着是 M2 个整数(B 型机器完成一次操作的时间,1..20)
SAMPLE INPUT (file job.in)
5 2 3
1 1 3 1 4
OUTPUT FORMAT
只有一行.输出两个整数:完成所有 A 操作的时间总和的最小值,和完成所有 B 操作的时间总和的最小值(A 操作必须在 B 操作之前完成).
SAMPLE OUTPUT (file job.out)
3 5