信息学集训队作业

1、长沙雅礼中m1 台A 类机器、m2长沙雅礼中m1 台A 类机器、m2 台B 类机器，每台机器加工一个原料（或者半成品很好解决了。时间复杂度为O(nm)，空间复杂度是O(n+m)【一第一约定有mAiAin工；并且A1A2A3Am假设已经有ki台机器加工完它分配到的原料所需要的时间是freei。接下来考虑如何分配第k+1 件原料。如果把第k+1 件原料分配到第ii台机器就要多花Ai的时间来加工它，令freei=freei+Ai。设free1, free2, , freem中的最小值是freep。如果说把第k+1 件原料放在第p 台机器上面无法得到最优解，由于所有的原料都是等价的，所以以后任何原料都

2、不能放在第 p 台机器。假设最优解中第 k+1（tp 把第k+1件原料从第tp ft=ft-因为fp=freep freet ftftft，所以maxfp,ftft。因此把第k+1 件原料放到第p 令freei=0（i=1,2,m） 求free1free2freem的最小值令把第k+1件原料从第tp ft=ft-因为fp=freep freet ftftft，所以maxfp,ftft。因此把第k+1 件原料放到第p 令freei=0（i=1,2,m） 求free1free2freem的最小值令输出二第二设某个A机器加工方案X使得n件原料的出产时间是：X=(x1, x2, , 假设n=4，看两个

3、加工结果：X1=(1,3,5X2=(1,2,6)。对第一问而言，无疑要更优秀的，因为X1 5 就能加工完、而X2 6如果作为第二问，考虑到还要放到 B 上面加要考虑的就不仅仅是xn了，前面x1,x2,xn-1设两个向量n X=(x1,x2,xn)，Y=(y1,y2,yn)，如果对于任意的xiyi，那么就说“优于 Y”，或者说 XY都满 过 X 也能得到最优方案。nii ，加工出来的半成品。也就是说A 类机器出产的顺序必须是 1,2,3,n设1.k-1m维向量F=f1f2fm k 令fi=fi+Ai，fp是f1,f2,fm的最小如果把第k件原料分配给第p台机器，那么机器的新状态就是newF=f1

4、f2 fp-1, fp+Ap, fp+1, , fm，并且Xk=fp+Ap。如果不把k 件原料分配给第 p 台机器，由fp是最小值，因此以后的原p上面加工（k 了可以令fp+oo。不妨设第k 件原料放到了第t 台机器上(tp)态是newF=(f1,f2,fp-。newFnewFXkXk。因此把第 kp台机器可以使 Xk最小；并且可以使得newF（也就是新的机器状态）最小，这样就能保证以后法完全确定下来了。设n X=(x1x2xn)（xn）关键是这些半成品还要放到B类机器上面加工。第一问中的原料是随叫随到的，也就是说任何时刻一台A 机器都可以从仓库里面取出一件原料。B A 机器还没有加T0TT0newFnewFXkXk。因此把第 kp台机器可以使 Xk最小；并且可以使得newF（也就是新的机器状态）最小，这样就能保证以后法完全确定下来了。设n X=(x1x2xn)（xn）关键是这些半成品还要放到B类机器上面加工。第一问中的原料是随叫随到的，也就是说任何时刻一台A 机器都可以从仓库里面取出一件原料。B A 机器还没有加T0TT00 的”在A 类机器上的加工情况！B A ) 显然这样的Y 2, , n，使得T=maxx1+yb1, x2+yb2, , xn+y