P2224 【[HNOI2001]产品加工】 DP

安利[个人博客](http://www.wjyyy.top/633.html) 像这种**进程DP**我是第一次见，不过只要把所有状态列出来，想做还是有好办法的。 我们首先看到，这个题同时维护**两个甚至是三个**进程，实在是不好想。我也是第一次看到有把数组下标当作最优状态求答案的，DP题见的应该还是越多越好。 我们试着用f[i][j]来维护当前加工第i个物品，A机器用时为j时B机器的最短用时。①我们不用担心排序问题，②也不用担心同时做会耽误某个空档的时间。①因为我们把这个模型当作一个**背包**，只管加入工件，不管添加顺序（背包不也是这样么）。②同时做的后效性问题：因为这里做的时候不用排序，所以我们把所有加入背包的**同时进行的进程**提到最前面去。 看这样一组数据： ``` 3 5 0 0 0 2 0 0 0 3 ``` 我们模拟这个过程，是这样的（分别编号为工件1,2,3）  因为我们用的是背包，所以等价于下面这样：**（贪心的思想）**  所以在没有顺序的时候，直接按背包做。我们的状态转移方程就是这样，不过状态只能单点转移而不是像背包那样只要比c[i]大都能转移：    $f[][]=∞ \ \ f[0][0]=0$    $f[i][j]=\min{\{ f[i-1][j]+t2[i],f[i-1][j-t1[i]],f[i-1][j-t3[i]]+t3[i]\}}$    因为这个题数据范围达到$5×6000^2=1.8\times 10^8$，超出1亿次，并且空间也会超128M，因此我们要优化枚举下界，并滚掉第一维。滚动比较好做，只要保存好转移t2时的状态，和背包相同。    枚举下界的调整：我们可以看出，因为状态是非严格单调递增的，所以我们如果发现对$∀i∈[0,k],f[i]=∞$，那么k以下的状态已经作废了，不会再被用到。此时我们的枚举下界down就可以调整到k了，并且每次做完检验是否可以继续更新。    同时要记得在输入的时候记录上界$(up+=\max {\{t1[i],t2[i],t3[i]}\})$，并记得每次置为∞防止用到过时状态（尤其是做t2时可能会碰到两层前的状态）。