斜率优化其实是一种思想,在 dp 的时候我们可能会遇到一类问题,这类问题依赖于之前的状态转移。因此多了一重枚举前一个元素的复杂度。而斜率优化是通过对一类特殊的最优化问题,尝试用决策点关于斜率的式子去除一些无用的决策,从而优化时间复杂度。
下面将给出几道习题来理解该算法。
[SDOI2016] 征途
Statement
求 \(m^2\times \sum\limits_{i=1}^{m}\frac{(a_i-S/m)^2}{m}\),其中 \(a_i\) 是每天走的距离,\(S=\sum a_i\)。
Analysis
展开上式
\[\begin{align*} \text{原式} & =m^2\times\sum\limits_{i=1}^{m}\frac{a_i^2+(S/m)^2-2a_iS/m}{m} \\ \quad\quad & =m^2\times\big( \sum\limits_{i=1}^{m}\frac{a_i^2}{m} + \sum\limits_{i=1}^{m}\frac{S^2}{m^3} -2 \sum\limits_{i=1}^{m}a_i\frac{S}{m^2} \big) \\ \quad\quad & =m^2\times\big( \sum\limits_{i=1}^{m}\frac{a_i^2}{m}+\frac{S^2}{m^2}-2\frac{S^2}{m^2} \big) \\ \end{align*} \] 标签:frac,limits,big,sum,斜率,quad,优化 From: https://www.cnblogs.com/misterrabbit/p/17220001.html