斜率优化

大致思想：

将决策点视为若干二维平面上的点，将当前点的已知条件视为斜率，将 \(dp_i\) 视为截距。寻找经过某个点且斜率一定的直线的最小截距。（寻找最大截距时需要将 \(dp\) 取负，转化为最小，这样维护的凸包就始终是下凸包）

凸包的维护：

单调队列：

满足条件：满足抉择点的 \(x\) 坐标单调递增，\(i\) 的 \(k\) 值单调递增

李超线段树

k,b,y的转换

转换的常见思路：若 \(i\) 为当前点，\(j\) 为最优决策点。把只与 \(j\) 有关的部分设为 \(Y(j)\)；把 “由 \(i\),\(j\) 决定的部分中 \(y\) 的部分设为 \(X(j)\)”；把“由 \(i\),\(j\) 决定的部分中 \(i\) 的部分设为 \(K(i)\)”；把只与 \(i\) 有关的部分设为 \(b\).当然，有一些题目可能涉及到常数的计算，放入哪个部分都是可以的，为了方便，我常把它放入 \(b\)中.

实例:dp[i] = dp[j] - A * (s[i] - s[j]) * (s[i] - s[j]) - B * (s[i] - s[j]) - C;假设有这样一个递推式，那么会有如下的转换:

ll getx(int i) { return s[i]; }
ll gety(int i) { return dp[i] - A * s[i] * s[i] + B * s[i]; }
ll getk(int i) { return -2 * A * s[i]; }

DP过程

写出这道题的转移方程，将方程进行一些变形后把 \(k,b,y\) 求出。

对于每一个点 \(i\):

1. 根据 \(K(i)\),求出点 \(i\) 的最优决策点 \(j\).（寻找切线的过程）
2. 将 \(i\) 对应的点\((X(i),Y(i))\) 加入平面，并维护凸包。

求最终答案。