> 正值青春脑子灵, ______________
爷总算也会斜率优化辣!
从例题讲起, 先写个朴素的dp式子
\[ f_i\textrm{ 代表前i个玩具装箱后的最小代价} \\ f_i = \min\{f_j + (i - j - 1 + S_i - S_j - L) ^ 2\} \quad (j < i) \]
我们发现这狗东西是\(n^2\)的, 我们把式子化简一下
\[ f_i = \min\{f_j + [(i + S_i) - (j + S_j) - L - 1]^2\} \\ \text{令 }A_i = S_i + i,\, L' = L + 1,\, B_i = A_i + L'\\ f_i = \min\{f_j + (A_i - A_j - L')^2\}\\ f_i = \min\{f_j + (A_i - B_j)^2\}\\ f_i = \min\{f_j + A_i^2 - 2A_iB_j + B_j^2\}\\ f_i - A_i^2 = \min\{f_j - 2A_iB_j + B_j^2\} \]
我们发现我们基本上把与 i 相关的和与 j 相关的都分到了等式的两侧, 除了 \(2A_iB_j\)
我们发现如果我们把和 \(i\) 相关的和与 \(j\) 相关的部分分开之后, 有丶像一个一次方程:
我们设
\[ \begin{cases} y = f_i - A_i^2\\ x = B_j\\ k = 2A_i\\ b = f_j + B_j^2 \end{cases} \]