【学习笔记】斜率优化

# 费用提前 **例题 [P2365](https://www.luogu.org/problem/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$） 那么这个式子就可以直接用一维斜率优化了。