 减小字体
 增大字体
生产产品(product)
【题目描述】
在经过一段时间的经营后，dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架，而要开始自己生产产品了！产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时，为了保证安全和产品的质量，每台机器最多只能连续完成产品的L个步骤。也就是说，如果有一台机器连续完成了产品的L个步骤，下一个步骤就必须换一台机器来完成。现在，dd_engi的OI商店有史以来的第一个产品就要开始生产了，那么最短需要多长时间呢？
【输入】(product..in)
第一行有四个整数M, N, K, L
下面的N行，每行有M个整数。第I+1行的第J个整数为T[J,I]。
【输出】(product.out)
输出只有一行，表示需要的最短时间。
【输入样例】
3 2 0 2
2 2 3
1 3 1
【输出样例】
4
【数据规模】
对于30%的数据，M<=1000
对于80%的数据，M<=3000
|
您当前的位置：惠州一中电教科组 -> 信息奥赛 -> 奥赛试题 -> 文章内容
∷相关文章评论∷ （评论内容只代表网友观点，与本站立场无关！） [