/ Vijos / 题库 /

生产产品

生产产品

描述

在经过一段时间的经营后,dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架,而要开始自己生产产品了!产品的生产需要M个步骤,每一个步骤都可以在N台机器中的任何一台完成,但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同,它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时,为了保证安全和产品的质量,每台机器最多只能连续完成产品的L个步骤。也就是说,如果有一台机器连续完成了产品的L个步骤,下一个步骤就必须换一台机器来完成。现在,dd_engi的OI商店有史以来的第一个产品就要开始生产了,那么最短需要多长时间呢?
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题

格式

输入格式

第一行有四个整数M, N, K, L
下面的N行,每行有M个整数。第I+1行的第J个整数为T[J,I]。

输出格式

输出只有一行,表示需要的最短时间。

样例1

样例输入1

3 2 0 2
2 2 3
1 3 1

样例输出1

4

限制

1s

提示

对于50%的数据,N<=5,L<=4,M<=10000
对于100%的数据,N<=5, L<=50000,M<=100000

来源

第一届“OI商店杯” dd_engi原创题目

信息

ID
1243
难度
8
分类
动态规划 | 单调性DP 点击显示
标签
(无)
递交数
2412
已通过
339
通过率
14%
上传者

相关

在下列训练计划中:

RP++分类题库