斜率优化笔记

推式子比代码长。

1. P3195 [HNOI2008] 玩具装箱

第一步：写出暴力

设 $f_{i}$ 表示前 $i$ 个玩具的最小答案， $s_{i}$ 表示 $C$ 的前缀和。

f_{i} = {min}_{j = 1}^{i - 1} {f_{j - 1} + (i - j + s_{i} - s_{j - 1} - L)^{2}}

第二步：分流 & 拆式子

令 $f_{i, j} = f_{j - 1} + (i - j + s_{i} - s_{j - 1} - L)^{2}$ 。

即当 $i$ 从 $j$ 这个位置转移时的最小答案。

将只和 $i$ 有关的和只和 $j$ 有关的提出来。

令 $g_{i} = i + s_{i} - L^{[1]}$ ， $h_{i} = i + s_{i - 1}$ 。

$[1]$ ：常数项放哪边或者哪边都不放均可，由于待会还要拆平方，虽然最后会被消掉，但是哪边都不放中间的式子就会很长。

\begin{aligned} f_{i, j} & = f_{j - 1} + (g_{i} - h_{j})^{2} \\ = f_{j - 1} + g_{i}^{2} - 2 g_{i} h_{j} + h_{j}^{2} \end{aligned}

第三步：讨论后面的转移点比前面的更优的条件

若 $j_{1} < j_{2}$ ，且 $j_{2}$ 比 $j_{1}$ 更优，即 $f_{i, j_{1}} > f_{i, j_{2}}$ ：

\begin{aligned} f_{j_{1} - 1} + g_{i}^{2} - 2 g_{i} h_{j_{1}} + h_{j_{1}}^{2} & > f_{j_{2} - 1} + g_{i}^{2} - 2 g_{i} h_{j_{2}} + h_{j_{2}}^{2} \\ (f_{j_{1} - 1} + h_{j_{1}}^{2}) - (f_{j_{2} - 1} + h_{j_{2}}^{2}) & > 2 g_{i} (h_{j_{1}} - h_{j_{2}}) \end{aligned}

令 $y_{i} = f_{i - 1} + h_{i}^{2}$ ：

y_{j_{1}} - y_{j_{2}} > 2 g_{i} (h_{j_{1}} - h_{j_{2}})

$s$ 单调递增，所以 $h$ 也单调递增，所以 $h_{j_{1}} - h_{j_{2}} < 0$ ：

\frac{y_{j_{1}} - y_{j_{2}}}{h_{j_{1}} - h_{j_{2}}} < 2 g_{i}

左边这个式子就相当于平面内经过 $A (h_{j_{1}}, y_{j_{2}})$ 和 $B (h_{j_{2}}, y_{j_{2}})$ 的直线 $A B$ 的斜率（就是一次函数的 $k$ ），也就是说当这个斜率小于 $2 g_{i}$ 时， $j_{2}$ 更优。

第四步：单调队列维护

令 $K (j_{1}, j_{2}) = \frac{y_{j_{1}} - y_{j_{2}}}{h_{j_{1}} - h_{j_{2}}}$ 。

可以证明转移点间的斜率一定是单调递增的：

考虑反证法。当 $j_{1} < j_{2} < j_{3}$ ， $K (j_{1}, j_{2}) > K (j_{2}, j_{3})$ 时，假设 $j_{2}$ 是最优转移点。则 $j_{2}$ 优于 $j_{1} \Rightarrow K (j_{1}, j_{2}) < 2 g_{i}$ ， $j_{2}$ 也优于 $j_{3} \Rightarrow K (j_{2}, j_{3}) > 2 g_{i}$ ，即 $K (j_{1}, j_{2}) < 2 g_{i} < K (j_{2}, j_{3})$ ，与条件矛盾，故假设不成立。

运用单调队列的思想，维护队列中相邻两个点的斜率单调递增，且保证队头和队头后一个点的斜率 $> 2 g_{i}$ ，由于斜率单调递增，故前一个点总是优于后一个点，取队头就是答案。

所有情况的单调队列取法总结：

$K (j_{1}, j_{2}) < g_{i}$ ， $g_{i}$ 单调增：维护队头斜率大于 $g_{i}$ ，斜率单调增，转移取队头。
$K (j_{1}, j_{2}) < g_{i}$ ， $g_{i}$ 单调减：维护队尾斜率小于 $g_{i}$ ，斜率单调增，转移取队尾。
$K (j_{1}, j_{2}) > g_{i}$ ， $g_{i}$ 单调增：维护队尾斜率大于 $g_{i}$ ，斜率单调减，转移取队尾。
$K (j_{1}, j_{2}) > g_{i}$ ， $g_{i}$ 单调减：维护队头斜率小于 $g_{i}$ ，斜率单调减，转移取队头。

先删尾，再加入，再删头，再转移。

2.

简要题意：有一个长度为 $n \leq 10^{6}$ 长度的数轴，除 $0$ 号点外每个点上有个分数 $a_{i}$ 。任选跳跃策略，从 $0$ 号点跳到 $n$ 号点，从 $j$ 跳到 $i$ 的收益是 $a_{i} (i - j)$ ，求最大分数。

f_{i} = {max}_{j = 0}^{i - 1} {f_{j} + a_{i} (i - j)}

令 $f_{i, j} = f_{j} + i a_{i} - j a_{i}$ 。

若 $j_{1} < j_{2}$ ，且 $f_{j_{1}} < f_{j_{2}}$ ：

\begin{aligned} f_{j_{1}} + i a_{i} - j_{1} a_{i} & < f_{j_{2}} + i a_{i} - j_{2} a_{i} \\ f_{j_{1}} - f_{j_{2}} & < a_{i} (j_{1} - j_{2}) \\ \frac{f_{j_{1}} - f_{j_{2}}}{j_{1} - j_{2}} & > a_{i} \end{aligned}

其他情况 1：与斜率比较的对象没有单调性

其实很好处理，根据大于号和小于号，单调队列维护递增还是递减的四条规律仍然适用，但是不能再保证队头或队尾和比较对象的关系，所以变成单调栈，然后二分找就行了。

3. P4655 [CEOI2017] Building Bridges

w_{i} \leftarrow w_{i - 1} + w_{i}

f_{i} = {min}_{j = 1}^{i - 1} {f_{j} + (h_{i} - h_{j})^{2} + w_{i - 1} - w_{j}}

光速推柿子（因为没啥用），令 $G_{i} = h_{i}^{2} + w_{i - 1}$ ， $H_{i} = f_{j} + h_{j}^{2} - w_{j}$ ，得到：

H_{j 1} - H_{j 2} > 2 H_{i} (h_{j 1} - h_{j 2})

然后发现由于 $h$ 没有单调性，连斜率小于 / 大于一个对象的形式都写不出来。

其他情况 2：斜率也没有单调性

把式子推回去到这：

f_{i} = {min}_{j = 1}^{i - 1} {f_{j} + h_{i}^{2} - 2 h_{i} h_{j} + h_{j}^{2} + w_{i - 1} - w_{j}}

令 $k = - 2 h_{j}$ ， $b = f_{j} + h_{j}^{2} - w_{j}$ 。

f_{i} = h_{i}^{2} + w_{i - 1} + {min}_{j = 1}^{i - 1} {k h_{i} + b}

$min$ 里的可以用李超线段树维护。相当于查询 $x = h_{i}$ 时， $y$ 的最小值。由于插入的是直线而不是线段，所有数都是整数没有精度问题，而且只关心最小值的大小而不是编号，所以比模板好写多了。

不过要注意边界问题，第 $0$ 条直线的 $b_{0} = \infty$ 。

4. P4027 [NOI2007] 货币兑换

贪心，如果在第 $j$ 天买入并在第 $i$ 天卖出，那么肯定是在第 $j$ 天全买第 $i$ 天全卖最优。

设 $p_{i}, q_{i}$ 分别表示第 $i$ 天 $a, b$ 能买多少个：

p_{i} = \frac{f_{i} r_{i}}{a_{i} r_{i} + b_{i}}, q_{i} = \frac{f_{i}}{a_{i} r_{i} + b_{i}}

\begin{aligned} f_{i} & = max (f_{i - 1}, {max}_{j = 1}^{i - 1} {a_{i} p_{j} + b_{i} q_{j}}) \\ = max (f_{i - 1}, {max}_{j = 1}^{i - 1} {b_{i} (p_{j} \frac{a_{i}}{b_{i}} + q_{j})}) \end{aligned}

把右边那一部分看成一次函数，李超线段树维护即可。

其他情况 2.1： $x$ 坐标是小数

离散化即可，小心 unique 后炸精度。

斜率优化笔记

1. P3195 [HNOI2008] 玩具装箱

第一步：写出暴力

第二步：分流 & 拆式子

第三步：讨论后面的转移点比前面的更优的条件

第四步：单调队列维护

2.

其他情况 1：与斜率比较的对象没有单调性

3. P4655 [CEOI2017] Building Bridges

其他情况 2：斜率也没有单调性

4. P4027 [NOI2007] 货币兑换

其他情况 2.1： $x$ 坐标是小数

更多类似题目

1/2. P3628 [APIO2010] 特别行动队 / SP15648 APIO10A - Commando

3. P5017 [NOIP2018 普及组] 摆渡车

4. P2900 [USACO08MAR] Land Acquisition G

斜率优化 笔记 ​

1. P3195 [HNOI2008] 玩具装箱 ​

第一步：写出暴力 ​

第二步：分流 & 拆式子 ​

第三步：讨论后面的转移点比前面的更优的条件 ​

第四步：单调队列维护 ​

2. ​

其他情况 1：与斜率比较的对象没有单调性 ​

3. P4655 [CEOI2017] Building Bridges ​

其他情况 2：斜率也没有单调性 ​

4. P4027 [NOI2007] 货币兑换 ​

其他情况 2.1：x 坐标是小数 ​

更多类似题目 ​

1/2. P3628 [APIO2010] 特别行动队 / SP15648 APIO10A - Commando ​

3. P5017 [NOIP2018 普及组] 摆渡车 ​

4. P2900 [USACO08MAR] Land Acquisition G ​

斜率优化笔记

1. P3195 [HNOI2008] 玩具装箱

第一步：写出暴力

第二步：分流 & 拆式子

第三步：讨论后面的转移点比前面的更优的条件

第四步：单调队列维护

2.

其他情况 1：与斜率比较的对象没有单调性

3. P4655 [CEOI2017] Building Bridges

其他情况 2：斜率也没有单调性

4. P4027 [NOI2007] 货币兑换

其他情况 2.1： $x$ 坐标是小数

更多类似题目

1/2. P3628 [APIO2010] 特别行动队 / SP15648 APIO10A - Commando

3. P5017 [NOIP2018 普及组] 摆渡车

4. P2900 [USACO08MAR] Land Acquisition G