想更加深入理解：Xing-Ling
什么是斜率优化？？
顾名思义呗，就是利用斜率的性质对 \(dp\) 进行优化
一般能斜率优化的 \(dp\) 一般长这样 \(dp[i] = min/max(a[i]*b[j] + c[j] + d[j])\) (b必须严格单调)
发现其中有一项是乘 (\(a[i]*b[j]\)) 所以单调队列优化就不再适用了，所以有了斜率优化
栗题
要输出 \(N\) 个正数字 \(a[N]\)，输出的时候可以连续的输出，每连续输出一串， 它的费用是 ：这串数字和的平方加上一个常数 \(M\)
求最小的费用
\(0 \leq n \leq 500000, 0 \leq M \leq 1000\)
solution
状态
\(dp[i]\) 表示输出到 \(i\) 的时候的最小花费，\(S[i]\) 表示从 \(a[1]\) 到 \(a[i-1]\) 的数字和
转移
枚举上一次输出的位置 \(j\) 就好了
时间复杂度
\(O(n^2)\)
考虑优化
上面的式子，我们可以发现，如果去掉 \(min\)，式子的本质就是找一个 \(j\) 使得 \(dp[i]\) 最小
那么我们去掉 min，且存在 \(j, k(j>k)\) 使得从 \(j\) 转移比从 \(k\) 转移更优
把 \(j\) 和 \(k\) 分别代入上面的式子中，可以得到
\(dp[j]+(S[i+1]?S[j])^2+M< dp[k]+(S[i+1]?S[k])^2+M\)
把式子展开，就是这么一个玩意
\(dp[j]+S[i+1]^2?2*S[i+1]*S[j]+S[j]^2+M < dp[k]+S[i+1]^2?2*S[i+1]*S[k]+S[k]^2+M\)
移项合并同类项
\((dp[j]+S[j]^2)?(dp[k]+S[k]^2)<2*S[i+1]*(S[j]?S[k])\)
因为 \(j > k\) 所以 \(S[j] - S[k] > 0\)，直接除过去就好了
\(\frac{(dp[j]+S[j]^2)?(dp[k]+S[k]^2)}{(S[j]?S[k])} < 2*S[i+1]\)
设 \(f[x]=dp[x]+S[x]^2\)
然后式子就成了
\(\frac{f[j] - f[k]}{s[j]-s[k]} < 2*s[i+1]\)
所以当 j > k 的时候，若\(\frac{f[j] - f[k]}{s[j]-s[k]} < 2*s[i+1]\) \(j\) 就比 \(k\) 更优
把 \((s[i],f[i])\) 看成一个点，左边就像这个玩意\(\frac{y_j - y_k}{x_j - x_i}\) （这不是斜率么）
当每一个 dp 值求出来之后，它的 f 值也跟着确定，我们就可以在空间中绘制出点 \((s[i],f[i])\) 这个点代表已经求出dp 值的一个点
当我们要求解 \(dp[t]\) 时，如果集合里存在这样三个点
他们和 \(2S[t+1]\) 的关系有三种
\(\frac{f[j] - f[k]}{s[j]-s[k]} > \frac{f[i] - f[j]}{s[i]-s[j]} > 2*s[t + 1]\)
此时 j 比 i 优，k 比 j 优
$\frac{f[j] - f[k]}{s[j]-s[k]} > 2*s[t + 1] >\frac{f[i] - f[j]}{s[i]-s[j]} $
此时 i 比 j 优，k 比 j 优
$2*s[t + 1] > \frac{f[j] - f[k]}{s[j]-s[k]} >\frac{f[i] - f[j]}{s[i]-s[j]} $
此时 i 比 j 优，j 比 k 优
发现 j 永远都不可能为最优解，所以 j 这个决策点就没有用了
可以得出一个规律，要维护一个凸包（只有凸包上的点才对转移起作用）
怎么维护凸包？？
由上图就可以知道，当 k => j 的斜率大于 j => i 的斜率，就把 j 删掉
得到这么一个凸包
单调队列优化
\(S[i]\) 满足单调性，所以这个斜率也是单调递增的，所以如果两个决策点的斜率小于当前斜率，那么前面那个决策点就没有用了，直接弹出队列，直到弹到有用的点就好了（手动模拟一下就好）
斜率不单调情况
因为斜率不单调了，所以就不能用单调队列优化了，所以就要用二分查找决策点
上图 \(j->i\) 的斜率 \(>2S[t+1]\) 且的斜率 \(<2S[t+1]\) 从图形特点我们可以发现 j 点比所有比 k 小的点都优，比所有比 i 大的也优，所以 j 就是枚举之后的答案
dp 式 \(dp[i] = min\lbrace dp[j]+(S[i+1]?S[j])^2 + M \rbrace\)
去掉 min 得到 \(dp[i] = dp[j] + S[i+1]^2 - 2*S[i+1]*S[j] + S[j]^2 + M\)
因为 i 是枚举的，所以与 i 有关的项就是已知的了，只有 \(j\) 是未知的
乘的那一项 \(S[j]\) 看作 \(X\)， \(2*S[i+1]\) 看成 \(K\) ， \(S[j]^2 + dp[j]\) 为 \(Y\) ，\(dp[i] - M - S[i + 1]^2\) 为 \(b\)
\(b = K*X + Y\)
很显然，那么 dp 式可以看成一条直线
因为是让 \(dp[i]\) 最小，也就是让 \(b\) 最小，当直线斜率一定时让直线的截距尽量小
可以想象为一条斜率已知的直线不断向上平移，碰到的第一个点就是最优的决策点
原文：https://www.cnblogs.com/Arielzz/p/14407207.html