UC知道动态规划题目
来源：百度知道 编辑：UC知道 时间：2024/04/28 13:19:00
产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时，为了保证安全和产品的质量，每台机器最多只能连续完成产品的L个步骤。也就是说，如果有一台机器连续完成了产品的L个步骤，下一个步骤就必须换一台机器来完成。
输入格式 Input Format
第一行有四个整数M, N, K, L
下面的N行，每行有M个整数。第I+1行的第J个整数为T[I,J]。
对于50%的数据，N<=5，L<=4，M<=10000
对于100%的数据，N<=5， L<=50000，M<=100000
输出格式 Output Format
输出只有一行，表示需要的最短时间。
麻烦详细分析一下过程，特别是怎么处理不连续L次，谢谢
你那个做法和我开始的时候一样，这是不对的，当time[j]==L时采用min{opt(i-1),p}+k与min{opt(i-m),p}+k+t[i-m+1,j]+...+t[i,j],m>1 无法判断
输入格式 Input Format
第一行有四个整数M, N, K, L
下面的N行，每行有M个整数。第I+1行的第J个整数为T[I,J]。
对于50%的数据，N<=5，L<=4，M<=10000
对于100%的数据，N<=5， L<=50000，M<=100000
输出格式 Output Format
输出只有一行，表示需要的最短时间。
麻烦详细分析一下过程，特别是怎么处理不连续L次，谢谢
你那个做法和我开始的时候一样，这是不对的，当time[j]==L时采用min{opt(i-1),p}+k与min{opt(i-m),p}+k+t[i-m+1,j]+...+t[i,j],m>1 无法判断
这题很明显要用到队列优化，楼主既然你能再没有L约束下做出，我们可以考虑做一个B数组，B[I，J]表示连续I次在J机器上做的最优值，不断维护，最优解即存与B中最小值，不明白QQ46468795
状态必须为三维的M(a,b,c)表示第a个步骤，第b台机器做，它已经连续工作了c个时间片。问题自然明了了。加油，回答不在多，在精