斜率优化

[[TOC]]

前置知识:线性规划

斜率优化的思想其实和高中数学的线性规划有相似之处，因此建议没学过的同学先了解一下线性规划

这个视频讲解了高中的线性规划的相关知识 https://www.bilibili.com/video/BV1qg4y1v7Xy?p=4

一元一次函数:$y = k \cdot x + b$,它的函数图像如下所示

其中$k,b$为定值,$k$为直线的斜率

由图可知如下的事实:

1. 这条直线$l$上的所有点$(x_l,y_l)$都符合:$y_l - k \cdot x_l ==d$或者反过来说:在坐标 轴上所有符合$y - k \cdot x = d$的点会组成一条直线,这条直线就是$l$
2. $B$为直线$l$与$y$轴的交点,同时也是直线$l$上的点,所以$y_B - k \cdot x_B = d$,此时$x_B == 0$, 所以得到: $y_B = d$

我们把这个距离称为截距.也就是说:直线$l$上的所有点$y_l - k \cdot x_l$的值就是这个截距.

斜率优化

问题: 如下图所示,有多个点$a_i$分布在坐标轴上,有一条直线$y = k \cdot x + b$,其中$k>0$且为定值,$b$可以变化(这意味着,直线可以上下平移),那么如何选择一点$a_i$,使直线经过该点时,使$b$值,也就是截距最小?

当我们选取一了一条直线,那么这条直线的斜率$k$就是固定的,此时只能上下平移的去移动这条直线,那么这个直线的截距$b$就是变化的.根据[ Rbook: 单调队列]的思想:++排除不可能的点++.我们不禁会想哪些点是不可能的点?

从候选的点集中任意取三个点$a,b,c$,如下图所示. 设$K(i,j)$为点$i,j$之间的斜率,即$K(i,j) =\frac{\varDelta y}{\varDelta x} = \frac{y_j - y_i}{x_j - x_i}$. 且这三个点满足发下的条件:

1. $x_a < x_b < x_c$
2. $K(a,b) = k_1 > k_2 =K(b,c)$

::: oneline

:::

入门: 玩具装箱

题目地址: [ luogu P3195: [HNOI2008] 玩具装箱]

解析

根据题目的意思可以很轻松的写出状态转移方程

其中,$sum[i] = \sum\limits_{1}^{i}{C_k}$,也就是前缀和.显然如果直接按这个方程来做,复杂度为$O(n^2)$

使用 斜率优化

发现公式$(1)$是一个关于两个变量$i,j$二元公式.其中变化的只有$j$,如果我们可以把是的变化拆分成两个部分$(X(j),Y(j))$,那么$j \in [1,i-1]$的每一次变化都会产生一对点,这些点都分布在平面上.

且我们想到得到的值是:$min\{k \cdot X(j) + Y(j)\}$,$k$为定值,那不就是求斜率为$k$的直线经过那对点可以得到小截距吗?那么问题就为上面斜率问题.

设

$$\begin{aligned} k(i) &= sum[i] + i - L -1 \\ X(j) &= sum[j] + j \end{aligned}$$

则可以得到

$$\begin{aligned} dp[i] &= \min\{dp[j]+(k(i) - X(j)) ^2\} \\ &= \min\{dp[j] + k(i)^2 - 2\cdot k(i) \cdot X(j) + X(j)^2\} \\ &= \min\{\fcolorbox{red}{aqua}{$ - 2\cdot k(i) \cdot X(j) + dp[j] + X(j)^2$} + k(i)^2\} \end{aligned}$$

再设

$$\begin{aligned} Y(j) \quad &= \quad dp[j] + X(j)^2 \end{aligned}$$

因为$k(i)$是定值,所以可以把$k(i)^2$移出来,则得到

$$dp[i] = \min\{\fcolorbox{red}{aqua}{$ - 2\cdot k(i) \cdot X(j) + Y(j) $}\} + k(i)^2$$

我们注意到\fcolorbox{red}{aqua}{$- 2\cdot k(i) \cdot X(j) + Y(j) $}形如z = kx+y, 我们设直线l(j)表示为:

$$l(j) = -2 k(i)\cdot X(j) + Y(j)$$

于是就得到

$$dp[i] = \min\{\fcolorbox{red}{aqua}{$ l( j ) $}\} + k(i)^2$$

显然我们要求的是\min\{l(j)\}, 1 \leqslant j < i,这个公式表示的意思就是: 我们要求直线方程线性规划$l(j)$的最小值

定义域为$j \in [1,i)$之间形成的点集$P:\{(X(1),Y(1)), (X(2),Y(2)), \cdots \}$

对于点集$P$中的每一个点$p$,都会有一条斜率为$k(i)$的直线经过$p$,直线上的点 代入公式$k \cdot x + y$的值一样 ,而它们的值就是截距

所以我们只需要找到最小的截距

同时,基于上面的公式,我们可以知道以下事实:

• $k(i)$值为正值,且随着$i$单调增加

证明 需要维护一个凸包

凸包上的哪个点是答案

凸包上的如何添加点

所以

我们需要维护一个下凸壳

且壳上的点斜率递增

1. 在壳上找到最优点
2. 在壳上添加新的点

更一般的公式推断

我们有一个这样的状态转移方程

• $X(j) \cdot k(i)$ 表示既与$i$有关又与$j$有关的项,因为$i$是固定的,通常$X(i)$的值也是定值
• $d(j)$ 表示只与$j$有关的项
• $B(i)$ 表示只与$i$有关的项,因为$i$是固定的,通常这个项的值也是定值

这样就可以看成这样的一条直线的公式

$$\colorbox{aqua}{ $ l_j \Rarr y = k(i) \cdot x + d(j) $}$$

那可以把原式子写成

\begin{equation} dp[i]=\min\limits_{j\in[l,r]}{\colorbox{aqua}{ $l_j(k(i) )$ } }+d(i) \end{equation}

所以对于每一个状态$i$,可以得到对应的$k(i)$,那么根据$l_j$就得到了对的值

也就是$l_j$这条直线的线性规划

对于本题来说

\begin{equation} dp[i]=\min\limits_{j\in[l,r]}{\colorbox{aqua}{ $l_j(k(i) )$ } }+d(i) \end{equation}

X(j) 是 K(i) 是

为什么我们需要维护一个下凸壳

? 那么第一个满足条件的P值 如何求解最值,找到第一个斜率大于$k(i)$的点

为什么要维护一个单调队列

单调队列如何添加点

如何得到头(update)

TODO

dp[0]应该是什么值?

方法2 : 推理法

TODO

我需要使用asymoto 画图 所以需要 asymoto的笔记

代码1: 朴素

#include <ios>

代码2: 模块

参考

• P3195 [HNOI2008]玩具装箱TOY（斜率优化入门） - hhz6830975 的博客 - 洛谷博客