斜率优化dp

斜率优化

斜率优化，一种优化 1D/1D 转移 dp 的方式，即将转移方程化为一次函数 $y=kx+b$ 的形式，再利用建模转化，将转移变成在某些数据结构上，比如单调队列、单调栈、李超树的操作，以此来优化转移时间复杂度。

一般来说（我感觉）斜率优化的转移方程里常常见到 $s_is_j$ 的形式。

例子：AT_dp_z Frog 3

容易写出 dp 方程

$$dp_i=\min\{dp_j+(s_i-s_j)^2+c\}$$

化简得到

$$dp_i-s_i^2-c=dp_j+s_j^2-2s_i\cdot s_j$$

发现 $s_i$ 单调递增，即作为斜率的 $2s_i$ 单调递增，利用单调队列维护凸包可以做到 $O(n)$。

例子：P2365&P5785 任务安排两件套

P2365 可以用暴力过去。

首先考虑到时间花费中的 $s$ 依赖于前面的决策段数，这不利于进行转移（暴力就无所谓了 XD），因此考虑把划分的时间额外开销进行贡献转化。考虑如果在这里划分，后面的所有部分都会有贡献，其贡献是 $s\cdot\sum\limits_{j=i}^nf_j$。

然后可以写出转移方程了。这里 $t_i>0$，因此前缀和是单增的，因此可以使用单调队列 $O(n)$。

然而在 P5785 中，$|t_i|\le2^8$，这表明 $t_i$ 不保证是正的（唐氏吗完成任务还倒贴时间了是吧），此时斜率不保证单增（但能得 60 分），因此拿二分队列做就可以了，时间复杂度 $O(n\log n)$。

更加劲爆的例子：P1721 国王饮水记

更详细的介绍可见这个课件。

Lemma 1 你发现如果一个水位 $h_i<h_1$，那么这个水位一定不会造成任何贡献。直接删掉！

Lemma 2 每个水缸最多会和 $1$ 连接一次。因为连接一次后他俩就一样高了，不会再造成贡献了。

Lemma 3 每次联通的时候都会有 $1$。可以证明 Lemma 2 与 Lemma 3 是等价的。

Lemma 4 当 $k\rightarrow\infty$ 时最优操作为将 $h_i$ 从小到大排序后依次向上一个一个取平均。

你发现一次操作可以被拆成若干次 $1$ 节点与单个节点的平衡，而有式子

$$\dfrac{h_1+h_2}{2}+h_3\ge\dfrac{h_1+h_3}{h_2}$$

此处 $h_1<h_2<h_3$。

于是对于任意两个节点，一定是水量小的与 $1$ 先连接，再让水量大的连接。

---

非常自然地想到要对 $h$ 排序并去掉比 $h_1$ 小的元素。

有了这些性质可以敲出一个 $O(k3^n)$ 的状压 dp 来。

同时根据 Lemma 2,4 可以知道有效操作数量不会超过 $O(n)$，直接取 $\min$ 是对的。

写一个取最大 $K$ 个的贪心。等等，为什么我的得分比 $45$ 高这么多？——《NOI2016 国王饮水记 讲课ppt》

---

然后又有 $3$ 个重要的定理：

Lemma 5 每次操作选择的城市的最小水量一定大于上一操作的最大水量。否则你交换两个逆序的城市按照 Lemma 4 会变得更优。

Lemma 6 每次操作选择的一定是个区间。可以找规律对吧如果不是区间，那么把选择的最小水量城市换成任意一个断点都会变优。

Lemma 7 每次操作选择的区间连续。否则把左边区间向右移一定更优。

---

到这里转移变成区间了！

设 $dp_{i,j}$ 表示考虑到第 $i$ 个城市并且进行了 $j$ 次操作的最大水位，则有转移方程

$$dp_{i,j}=\max_{0\le k<i}\left\{\dfrac{dp_{k,j-1}+s_i-s_k}{i-k+1}\right\}$$

其中 $s_i$ 表示水量前缀和。

直接转移时间复杂度是 $O(n^2kp)$ 的。

你重新审视一下这个方程，设最优决策点为 $k$，给他变形得到

$$\begin{aligned}dp_{i,j}&=\dfrac{dp_{k,j-1}+s_i-s_k}{i-k+1}\\&=\dfrac{s_i-(s_k-dp_{k,j-1})}{i-(k-1)}\end{aligned}$$

虽然这不是斜率优化常见的式子形式 $y=kx+b$，但是这个却是斜率的表达式

$$k=\dfrac{y(i)-y(j)}{x(i)-x(j)}$$

因此也可以斜率优化，其中凸包上的点为 $(k-1,s_k-dp_{k,j-1})$。

当前转移点就是过点 $(i,s_i)$ 的凸包上点的斜率最小值，可以用三分来求出，时间复杂度被优化到 $O(nkp\log n)$。

---

但是这样只能过 $70$ 分，考虑继续优化。

Lemma 8 决策点有单调性。

假设两个决策点为 $k>l$ 且 $k$ 比 $l$ 优，按照定义有 $dp_{k,j-1}\ge dp_{l,j-1}$。然后你对不等式做一个变形

$$\begin{aligned}(k-l)(s_k-s_l+dp_{k,j-1})&\ge(i-l+1)h_k+(k-l)h_{i+1}\\&\ \ \ \ \ -(i-k-1)(dp_{k,j-1}-dp_{k-1,j-1})\\&\ge(i-l+1)[h_k-(dp_{k,j-1}-dp_{k-1,j-1})]\end{aligned}$$

得证。

---

得到决策单调性之后利用单调队列可以少一个 $\log$。

还可以优化？

注意到水量高度互不相同，可以知道每一次操作的区间长度不会大于上一次的区间长度。感性的想就是越往后走高度越大，显然拿更少的位置来平分会更优。另一个奇妙的性质是：长度大于 $1$ 的决策区间很少，只有 $O(\log\frac{nk}{\Delta})$，其中 $\Delta=\min\{h_i-h_{i-1}\}$。

为什么我也不会了。

这样子就不用 dp $k$ 层了，只需要 dp 这么多层就可以了。

时间复杂度是 $O(np\log nh)$。

但是居然还有 $O(n(\log^3nh+p))$ 的做法在 ppt 里？太奆了不会。

给个高精小数 Decimal 类还是很善良的！

一些很蠢的事情

警钟爆破队长

求斜率的常见计算方式是

$$k=\dfrac{y(i)-y(j)}{x(i)-x(j)}$$

但是这样是要用实数的，爆精度就似了。考虑移项之后用乘法保住精度。

但是很重要的一个细节是 $x(i)-x(j)$ 不要写反，一定是大减小，不然移项的时候会导致不等式方向变化就似了。

警钟爆破队员 1 号

@P2120。

你发现这个题很简单对吧！

考虑设 $dp_i$ 表示在第 $i$ 个工厂上建造仓库的最小开支。

但是你发现转移的时候 $val(l,r)$ 不易计算，需要展开一下。

具体的：

$$\begin{aligned}\sum_{i=l}^rp_i\cdot dis(i,r)&=\sum_{i=l}^rp_i(x_r-x_i)\\&=x_r\sum_{i=l}^rp_i-\sum_{i=l}^rp_ix_i\end{aligned}$$

我们记 $s1_i=\sum\limits_{j=1}^ip_j$，$s2_i=\sum\limits_{j=1}^ip_jx_j$，那么上式化简为

$$x_r(s1_r-s1_{l-1})-(s2_r-s2_{l-1})$$

你写出 dp 方程：

$$dp_i=\min_{0\le j<i}\{dp_j+val(j-1,i)+c_i\}$$

设 $j$ 是转移最优决策点则有

$$dp_i=dp_j+x_i(s1_i-s1_j)-(s2_i-s2_j)+c_i$$

化简得

$$dp_i-x_is1_i-s2_i-c_i=dp_j+s2_j-x_i\cdot s1_j$$

这就是斜率优化的板子了，注意到 $x_i$ 单调递增于是直接 $O(n)$。

于是你迅速地敲完了这个题，测试样例，通过了！

然后你提交，诶，怎么 Unaccepted 100分啊？你很生气。

你百思不得其解，打开讨论区，全是诸如被hack力，求调（悲此类的东西。你随便打开了一个，看到这样一句话：

最后可能会有一长条 $p_i=0$ 的可（毒）爱（瘤）工厂，最后答案是尾巴上所有 $p_i=0$ 的工厂的 dp 值取 $\min$。

你怀着愤恨的心情去骂 ZJOI2007 的出题人没有良心。