P2224 【[HNOI2001]产品加工】 DP

· · 题解

安利个人博客

像这种进程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时可能会碰到两层前的状态）。