Vijos 1243 生产产品 解题报告

定义f[i,j]为生产前j个产品，最后一个在i机器上生产的最少耗费，容易推出朴素的状态转移方程。主要难点在于有同一台不能连续超过生产l个产品的规定，优化时间复杂度的关键在于降低在这l个状态中决策的时间复杂度。

定义g[i,j]为生产前j个产品，第j个在i机器上生产且第j-1个不在i机器上生产的最少耗费。易得f[i,j]=min(f[i,j],g[i,t]+sum[i,j]-sum[i,t])(j-l<t<=j);sum[i,j]表示在i机器生产前j个产品的费用和。可以发现影响决策的是g[i,t]-sum[i,t]的值，维护一个单调队列保存g[i,t]-sum[i,t](j-l<t<=j)的值，每次决策时取队首元素即可。

朴素的维护方法是利用堆来实现取最小的操作并在log(l)的时间内完成插入和删除操作。对于本题来说这一时间复杂度O(nnmlog(l))是可以接受的，但存在更优的方法使实际时间复杂度以及编程复杂度下降。显然当g[i,t]-sum[i,t]=g[i,p]-sum[i,p]时，若t>p，则保留p的状态就没有意义了。因此可以利用指针来维护一个单调队列，每次插入时二分寻找符合条件的插入点，并将队尾指针指向此。然后检查队首元素位置是否符合要求，如不符合则将队首指针后移，这样即可以实际时间复杂度远低于log(l)的代价完成队列的维护。对于本题的数据这一优化的效果非常明显。

R1216193 Accepted 100 From IwfWcf－ P1243 FPC Vivid Puppy 2009-4-21 2:26:30