斜率优化 DP

斜率优化 DP 有个很套路化的形式：

这样的形式：

dp[i]=max⁡j:conditiondp[j]+f(i)×g(j)dp[i] = \max_{j:\text{condition}} dp[j] + f(i)\times g(j)

求 max 的话，通常是维护点集的上凸壳

或者……

dp[i]=min⁡j:conditiondp[j]+f(i)×g(j)dp[i] = \min_{j:\text{condition}} dp[j] + f(i)\times g(j)

求 min 的话，通常是维护点集的下凸壳

例题

Luogu P5504

首先我们需要想到的一点是：如果取的是 [l,r][l,r] 的贝壳，那么选择的 s0=sizel=sizers_0=size_l=size_r . 如果不这样做，考虑选取的是 [l,r][l,r] 而 l<k<r,sizek=sizerl\lt k\lt r, size_k=size_r，那么，我们完全可以把这一段拆成 [l,k−1],[k,r][l,k-1],[k,r] 两段，答案肯定更优。

然后，我们考虑 dp[]dp[] 式子，令 dp[]dp[] 就是我们想要的最大柠檬数，把它想象成一个总是从前缀转移的 dp，可以列出

c=sizeidpi=max⁡j≤i∧sizej=c(dpj−1+c×(sumc,i−sumc,j+1)2) c=size_i\\ dp_i=\max_{j\le i\land size_j=c}\Bigg( dp_{j-1} + c\times (sum_{c,i}-sum_{c,j}+1)^2 \Bigg)

其中 sumc,isum_{c,i} 表示 1∼i1\sim i 里 size 为 cc 的贝壳数量。

我们把式子展开成斜率优化的形式，首先拿掉 max⁡\max：

dpi=dpj−1+c×(sumc,i2+(sumc,j−1)2−2⋅sumc,i⋅(sumc,j−1)) dp_i=dp_{j-1}+c\times \Big( sum_{c,i}^2+(sum_{c,j}-1)^2-2\cdot sum_{c,i}\cdot (sum_{c,j}-1) \Big)

由于 sizej=sizeisize_j=size_i，我们可以适当的替换 cc 为 sizejsize_j，然后写成 b(i)=y(j)−k(i)⋅x(j)b(i)=y(j)-k(i)\cdot x(j) 的形式

dpi−c⋅sumc,i2⏟b(i)=dpj−1+c⋅(sumc,j−1)2⏟y(j)−(2⋅c⋅sumc,i)⏟k(i)⋅(sumc,j−1)⏟x(j) \underbrace{dp_i-c\cdot sum_{c,i}^2}_{b(i)}=\underbrace{dp_{j-1}+c\cdot (sum_{c,j}-1)^2}_{y(j)} - \underbrace{(2\cdot c\cdot sum_{c,i})}_{k(i)}\cdot\underbrace{\Big( sum_{c,j}-1 \Big)}_{x(j)}

因为我们的 dpidp_i 要求的是 max⁡\max，而 sumc,j−1sum_{c,j}-1 是递增的，所以，我们需要维护的是上凸壳，插入的点的坐标是 (sumc,j−1,dpj−1+c⋅(sumc,j−1)2)\Big( sum_{c,j}-1, dp_{j-1}+c\cdot (sum_{c,j}-1)^2 \Big).

Code

要注意的代码细节：

  1. 由于 jj 其实可以选择 ii 自己（即只取长度为 11 的区间），所以我们需要先把 dpi−1dp_{i-1} 塞进凸壳里，再在凸壳上二分斜率判断（代码 49 行）
  2. 二分判断斜率的时候，要注意越界问题（即如果 mid=r−1mid=r-1，则此时 mid+1mid+1 会造成数组越界）.

    我这里的话，是在 convex hull 的末尾额外添加了一个点确保不会越界（绿色高亮和红色高亮），我这里的二分是 l + 1 < r 的写法。

    且 67 行的 r-- 也是为了避免越界。

  3. 此外如果用 mid 与 mid+1 的点之间的斜率，最后的转移点要取 mid+1mid+1，因为 mid ~ mid+1 的斜率 ≥k\ge k 而 mid+1 ~ mid+2 之间的斜率 <k\lt k.
JSOI2011 柠檬
JSOI2011 柠檬