一个启发是，对于一个 \(i\) 的两个转移 \(j,k\)，比较 \(j\) 与 \(k\) 的转移优劣。
可以用斜率优化的场景：对比后可以分拆出 \(slope(j,k)\le\texttt{只和i相关的一些东西}\) 的形式。
例如 P3195，首先写出转移方程
\(dp_i=\min\limits_{0\le j<i}\{dp_j+(s_i-s_j+i-j-1-L)^2\}\)
比较两个 \(j,k\)，选 \(j\) 不选 \(k\) 当且仅当
\[dp_j+((s_i+i-L-1)-(j+s_j))^2<dp_k+((s_i+i-L-1)-(k+s_k))^2 \]记 \(T=s_i+i-L-1\)，于是
\[dp_j+(T-(j+s_j))^2<dp_k+(T-(k+s_k))^2 \]\[dp_j+T^2-2T\cdot(j+s_j)+(j+s_j)^2 < dp_k+T^2-2T\cdot(k+s_k)+(k+s_k)^2 \]\[(dp_j+(j+s_j)^2)-(dp_k+(k+s_k)^2)<2T\cdot((j+s_j)-(k+s_k)) \]\[\dfrac{(dp_j+(j+s_j)^2)-(dp_k+(k+s_k)^2)}{(j+s_j)-(k+s_k)}<2T \]令 \(X(i)=i+s_i, Y(i)=dp_i+(i+s_i)^2\)，条件等价于
\[\dfrac{Y(i)-Y_j}{X(i)-X(j)}=\operatorname{slope}(j,k)<2T \]注意到 \(X(i)\) 单调，单调队列维护单调 slope 值，存储所有 \(<2T\) 的位置，每次队头即为最优转移点。
本质就是题解所说的，维护下凸壳，我比较懒不画图了。
另一个题是 P5785，用相同方法可以化简到
\(X(i)=i+sumf_i, Y(i)=dp_i-sumf_i\cdot s\)
注意到 \(X(i)\) 并非单调，所以需要维护整个下凸壳，然后二分找到 \(k_0<k<k_1\)，也就是第一个小于 \(k\) 的位置。
其他都没啥了。记个思想就行，其他操作都是模板。
标签：slope,le,cdot,dfrac,斜优,dp,单调,小记 From： https://www.cnblogs.com/liangbowen/p/18438124