P2224 【[HNOI2001]产品加工】 DP

2018-06-29 15:45:33


安利个人博客

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