To boldly go where no one has gone before.

【学习笔记】斜率优化

2019-09-03 22:21:21


费用提前

例题 P2365

这道题一眼看去就知道是个斜率优化。但是由于分组数会对后面的费用造成影响,所以决策是有后效性的。考虑如何写出朴素的动规方程,如果用$f[i][j]$表示前$i$个物品分成$j$组的费用,好像能够做,但是由于$n\leq 5000$,时间复杂度一下来到了$O(n^3)$。在这种情况下,第一反应是滚动掉一维,但是滚动以后虽然空间复杂度降低了,时间复杂度并不会发生变化;很明显必须要把$j$的枚举优化掉。

于是就有了费用提前思想:把后面物品的费用提前到前面的计算当中,这样在每次计算的时候,已经考虑了后面物品的费用变化,因此问题就变得没有后效性了。

观察:

$$f[i]=\min f[j]+(c\cdot S+sumt[i]-sumt[j])\cdot(sumf[i]-sumf[j])$$

其中$c$表示已经分的组数。考虑把式子部分展开:

$$f[j]+\underline{c\cdot S\cdot(sumf[i]-sumf[j])}+(sumt[i]-sumf[j])\cdot(sumf[i]-sumf[j])$$

如果除去带下划线的项,那么这个式子就是个标准的一维斜率优化式了。现在的问题是,如何不利用$c$就准确计算出完成时刻。

可以从这样的角度出发:前$i$个物品每多分一个组,后面的$[i+1,n]$物品每一组的完成时刻都会多$S$,那么费用就一定会增加$S\cdot(sumf[n]-sumf[i])$。这样就成功完成了去后效性。

如果用$f[i]$来表示考虑前$i$个物品时的当前最优费用和,则转移方程为:

$$f[i]=\min f[j]+(s_t[i]-s_t[j])\cdot(s_f[i]-s_f[j])+S\cdot (s_f[n]-s_f[i])$$

(由于式子太长,用$s_t$和$s_f$代替$sumt$和$sumf$)

那么这个式子就可以直接用一维斜率优化了。