斜率优化 | Cauphenuny's Blog

写出 $\text{dp}$ 方程后，要先判断能不能使用斜优，即是否存在 $function(i)*function(j)$
的项或者 $\frac{Y(j)-Y(j')}{X(j)-X(j')}$ 的形式。
通过大小于符号或者 $b$ 中 $dp[i]$ 的符号结合题目要求 $(\min/ \max)$
判断是上凸包还是下凸包，不要见一个方程就直接盲猜一个下凸。
当 $X(j)$ 非严格递增时，在求斜率时可能会出现 $X(j_1)=X(j_2)$ 的情况，此时最好是写成这样的形式：return Y(j)>=Y(i)?inf:-inf，而不要直接返回 $inf$ 或者 $-inf$ ，在某些题中情况较复杂，如果不小心画错了图，返回了一个错误的极值就完了，而且这种错误只用简单数据还很难查出来。
注意比较 $k_0[i]$ 和 $slope(j_1,j_2)$ 要写规范，要用右边的点减去左边的点进行计算（结合 $(3)$ 来看，可防止返回错误的极值），如果用的代数法理解，写出了 (X(j2)-X(j1))*k0<=Y(j2)-Y(j1) 或(X(j2)-X(j1))*k0<=Y(j2)-Y(j1)，而恰巧 $j_1,j_2$ 又写反了，便会出现等式两边同除了负数却没变号的情况。当然用 $k_0$ 和 $\frac {Y(j_2)-Y(j_1)}{X(j_2)-X(j_1)}$ 进行比较是没有这种问题的。
队列初始化大多都要塞入一个点 $P(0)$ ，比如玩具装箱 $\text{toy}$ ，需要塞入 $P(S[0],dp[0]+(S[0]+L)^2)$ 即 $P(0,0)$ ，其代表的决策点为 $j=0$ 。
手写队列的初始化是 h=1,t=0，由于塞了初始点导致 $t$ 加 $1$ ，所以在一些题解中可以看到 h=t=1 甚至是 h=t=0，h=t=2 之类的写法，其实是因为省去了塞初始点的代码。它们都是等价的。
手写队列判断不为空的条件是 h<=t ，而出入队判断都需要有至少 $2$ 两个元素才能进行操作。所以应是 h<t 。
计算斜率可能会因为向下取整而出现误差，所以 $slope$ 函数最好设为 $long$ $double$ 类型。
可能会有一部分的 $\text{dp}$ 初始值无法转移过来，需要手动提前弄一下，例如摆渡车
$\text{[P5017]}$ 。
在比较两个斜率时，尽量写上等于，即 <= 和 >= 而不是 < 和 >。这样写对于去重有奇效（有重点时会导致斜率分母出锅），但不要以为这样就可以完全去重，因为要考虑的情况可能会非常复杂，所以还是推荐加上 3 中提到的特判，确保万无一失。

（题单）

玩具装箱 toy [HNOI2008] [P3195]
土地征用 Land Acquisition G [P2900]
征途 [SDOI2016] [P4072]
Cats Transport [CF311B]
摆渡车 [NOIP2018] [P5017]
仓库建设 [ZJOI2007] [P2120]
序列分割 [APIO2014] [P3648]
任务安排 2 [Loj10185] [Poj1180]
锯木厂选址 [CEOI2004] [P4360]
特别行动队 [APIO2010] [P3628]
国王饮水记 [NOI2016] [P1721]

（以此处为分界线，上面都是 $X(j)$ 与 $k_0[i]$ 均单调的例子）

任务安排 3 [SDOI2012] [P5785] [Loj10186]
[Bzoj2726]（ X(j) 单调 k_0[i] 不单调）
高速公路 [P3994]（ X(j) 单调 k_0[i] 不单调。树上转移）
购票 [NOI2014] [P2305]（ X(j) 单调 k_0[i] 不单调。树上转移）
Building Bridges [CEOI2017] [P4655]（ X(j) 与 k_0[i]
均不单调）
货币兑换 [NOI2007] [P4027]（ X(j) 与 k_0[i] 均不单调）

（做题记录）

P4072(SDOI2016) 征途

给定 $n$ 个数 $a_{1\ldots n}$ ，划分成 $m$ 段，令方差为 $s$ ，求 $s \times m^2$ 的最小值

欢乐的推式子时间

设分成 $x_{1\ldots m}$ 。

$\begin{aligned} m^2s&=m^2\dfrac{(x_1-\overline x)^2+(x_2-\overline x)^2+\cdots+(x_n-\overline x)^2}{m}\\ &=m(\sum_{i=1}^m{x_i}^2+m\overline x^2-2\overline x\sum_{i=1}^mx_i)\\ &=m\sum_{i=1}^n{x_i}^2+(\sum_{i=1}^nx_i)^2-2(\sum_{i=1}^nx_i)^2\\ &=m\sum_{i=1}^n{x_i}^2-(\sum_{i=1}^nx_i)^2 \end{aligned}$

发现 $(\sum_{i=1}^nx_i)^2$ 是定值，就是求 $\sum_{i=1}^n{x_i}^2$ 的最小值

经典的斜率优化问题

设 $f(x,t)$ 表示将前 $x$ 个数划分成 $t$ 段，平方和的最小值。

设 $s_x$ 表示 $a_1+a_2+\ldots+a_x$ 的值

$\begin{aligned} f(x,t)&=\min_{1\le y<x}(f(y,t-1)+(s_x-s_y)^2)\\ &=\min_{1\le y<x}(f(y,t-1)+{s_x}^2+{s_y}^2-2s_xs_y)\\ &=\min_{1\le y<x}(f(y,t-1)+{s_y}^2-2s_xs_y)+{s_x}^2 \end{aligned}$

min 去掉，移个项，看的更清楚些

$f(y,t-1)+{s_y}^2=2s_xs_y+f(x,t)-{s_x}^2$

令 $B_x=f(x,t-1)+{s_x}^2$ ， $A_x=s_x$

那么就是求一个经过 $(A_y,B_y)$ 的点，斜率为 $2s_x$ ， $f(x,t)$ 就是截距加上 ${s_x}^2$ 。

找截距最小的直线，维护下凸包。

若 $(A_{y_2},B)$ 比更 $(A_{y_1},B)$ 优

则有 $\dfrac{(B_{y_2}-B_{y_1})}{A_{y_2}-A_{y_1}}<2s_x$

$s_x$ 单增，单调队列维护。

注意：维护凸包的时候记得用 slope(q[tail - 1], q[tail]) 不是 slope(tail - 1, tail)！！！！

~~挂了两遍了~~

P2120 (ZJOI2007)仓库建设

有 $N$ 个工厂，由高到底分布在一座山上．工厂 $1$ 在山顶，工厂 $n$ 在山脚.第 $i$ 个工厂有 $p_i$ 件产品，在第 $i$ 个工厂位置建立仓库的费用是 $c_i$ ．对于没有建立仓库的工厂，要将产品运往山下的仓库（即只能运往编号更大的工厂的仓库）。一件产品运送 $1$ 个单位距离的费用是 $1$ 。

假设建立的仓库容量都都是足够大的，且已知：
工厂 $i$ 距离工厂 $1$ 的距离 $d_i$ (其中 $d_1=0$ )；
工厂 $i$ 目前已有成品数量 $p_i$ ；
在工厂 $i$ 建立仓库的费用 $c_i$ 。

求最小费用（建造费用+运输费用）

设 $f(x)$ 表示在第 $x$ 个位置修仓库，将工厂 $1\ldots x$ 的产品全部运到仓库（不一定是仓库 $x$ ）的最小费用

易得转移方程

$f(x)=\min_{1\le y<x}(f(y)+\sum_{i=y+1}^{x}p_i(d_x-d_i)+c_x)$

化简得

$f(x)=f(y)+d_x\sum_{i=y+1}^{x}p_i-\sum_{i=y+1}^{x}d_ip_i+c_x$

不妨设 $a_x=\sum_{i=1}^{x}p_i$ ， $b_x=\sum_{i=1}^{x}d_ip_i$

则

$\begin{aligned} f(x)&=f(y)+d_x(a_x-a_y)-b_x+b_y+c_x\\ &=f(y)+d_xa_x-d_xa_y-b_x+b_y+c_x \end{aligned}$

$\begin{aligned} &\underbrace {f(y)+b(y)}=\underbrace{d_x}\underbrace{a_y}+\underbrace{f(x)-d_xa_x-c_x}\\ &\qquad Y\qquad\qquad K\quad\ \ X\qquad\qquad\quad B \end{aligned}$