斜率优化(Convex Hull Optimisation)

英文直译为 凸包优化, 指利用状态转移方程的特殊性质, 将决策转化为坐标系中的点, 维护下凸壳进行优化的技巧.

\(February~2021\) 清北学堂 DP-图论营, 讲斜率优化的时候我精准睡觉, 从开始睡到结尾, 成为开学后校内测试的眼泪.

问题转化

设有一类 DP 问题, 其转移方程形如

\[f_i = min/max(a_ib_j + f_j + c_i) \]

其中, \(a_i\), \(b_i\), \(f_i\) 单调

则可以使用斜率优化

将方程转化为函数, 变形成以 \(b_j\) 为自变量, \(f_j\) 为因变量的函数.

\[f_j = -a_ib_j + f_i - c_i \]

这时, 函数图像是一条以 \(-a_i\) 为斜率, \(f_i - c_i\) 为截距的直线, 经过点 \((b_j, f_j)\), 这个点被称作决策点

由于 \(-a_i\), \(-c_i\) 只和 \(i\) 有关, 所以对于某一个 \(i\), 最佳决策就是使图像截距最小/大的 \(j\), 问题转化成找一个点 \((b_j, f_j)\), 使经过它的斜率为 \(-a_i\) 的直线截距最小/大

上凸 \(\And\) 下凸

由于单调性的增减不会影响原理, 所以不失一般性, 我们假设 \(-a_i\), \(b_i\), \(f_i\) 单增, 且最优决策点使得直线截距最小

这样一来, 就有 \(P_{j + 1}\) 一定在 \(P_j\) 右上出现. 斜率 \(k_{j, j + 1}>0\)

分析问题的几何性质可以发现, 对于同一个 \(i\), 由于斜率一定, 所有决策点对应的直线都平行, 所有一个决策点比另一个优, 当且仅当这个点对应的直线在另一条之下; 一条线在另一条之下, 当且仅当这条线在另一条线上的一个点之下

容易发现, 如果 \(k_{j - 1, j} > k_{j, j + 1}\), 则 \(P_j\) 一定不是最优决策点, 因为如果 \(P_j\) 优于 \(P_{j - 1}\), 说明 \(P_{j - 1}\) 在直线 \(l_j\) 之上, \(k_{j - 1, j} < -a_i\). 又因为 \(k_{j - 1, j} > k_{j, j + 1}\), 所以 \(-a_i > k_{j, j + 1}\), \(P_{j + 1}\) 优于 \(P_j\); 同理, 当 \(P_j\) 优于 \(P_{j + 1}\) 时, 一定有 \(P_{j - 1}\) 优于 \(P_j\).

我们把上面 \(P_j\) 这种情况称作 上凸, \(P_j\) 不可能是最优决策, 所以最优决策只能出现在 下凸 的情况, 即 \(k_{j - 1, j} \leq k_{j, j + 1}\)

下凸壳

维护一个单调队列, 使得在队列中的点满足 \(k_{j - 1, j} < k_{j, j + 1}\) (从这时开始, 下标 \(j\) 特指队列中的下标), 这时候, 相邻点连成的斜率随k不断增大的折线就称作下凸壳. 下凸壳的性质是没有一个点位于其下, 在队列里的点位于下凸壳上, 不在队列里的点位于下凸壳内

容易看出, 对同一个 \(i\), 下凸壳的斜率为 \(-a_i\) 的切线的切点就是最佳决策点. 没有任何决策点在切线之下, 也就没有更优的决策了.

求解

下凸壳上点 \(P_j\) 是切点, 必须满足 \(k_{j - 1, j} \leq -a_i \leq k_{j, j + 1}\)

由于斜率 \(-a_i\) 也具有单调性, 每次决策时会将其最佳决策点前面的点删掉, 所以凸包总共会被遍历一次, 每个点也只会入队一次, 因此时间复杂度是 \(O(n)\)

需要注意的是, 由于新的决策点 \(P_i\) 需要入队, 所以必须在入队时保证下凸原则, 入队前删掉队尾的点 \(P_r\), 直到 \(k_{r - 1, r} \leq k_{r, i}\), 将 \(P_i\) 入队

例题Luogu3195

题面大意

\(n\) 个物品, 大小为 \(c_i\), 可以选取一段连续的物品 \((l, r)\) 装入容器, 容器大小为 \(sum_r - sum_{l - 1} + r - l\), 大小为 \(x\) 的容器花费 \((x - L)^2\), \(L\) 是常数. 求装下所有物品的最小总费用.

\(1 \leq n \leq 5 * 10^4, 1 \leq L, C_i \leq 10^7\)

状态设计

计算前缀和 \(sum_i\) 表示前 \(i\) 件物品总大小

\(f_i\) 表示前 \(i\) 个物品的最小花费, 写出方程

\[f_i = min(f_j + (sum_i - sum_{j} + i - j - L - 1)^2) \]

去掉取最小值, 整理

\[f_i = f_j + (sum_i + i - L - 1)^2 - 2(sum_i + i - L - 1)(sum_{j} + j) + (sum_{j} + j)^2 \]

设 \(t_i = sum_i + i - L - 1\), \(k_j = sum_{j} + j\), 则

\[f_i = f_j + {t_i}^2 - 2t_ik_j + {k_j}^2 \]

整理得

\[f_j + {k_j}^2 = 2t_ik_j + f_i - {t_i}^2 \]

得到以 \(k_j\) 为自变量, \(f_j + {k_j}^2\) 为因变量的函数. 因为 \(a_i > 0\), 所以 \(2t_i\), \(k_j\), \(f_j + {k_j}^2\) 单调递增, 可以使用斜率优化

表示出决策点的坐标

\[x = k_j\\ y = f_j + {k_j}^2 \]

斜率比较

\[k_{j - 1, j} < k_{j, j + 1}\\ \Downarrow\\ (y_j - y_{j - 1})(x_{j + 1} - x_j) < (x_j - x_{j - 1})(y_{j + 1} - y_j)\\ \]

\[k_{j - 1, j} < k\\ \Downarrow\\ y_j - y_{j - 1} < k(x_j - x_{j - 1}) \]

代码

int main() {
  n = RD();
  L = RD(); 
  sum[0] = 0;
  for (register unsigned i(1); i <= n; ++i) {
    a[i] = RD();
    sum[i] = sum[i - 1] + a[i];
    b[i] = sum[i] + i - L - 1;  //处理 t[i] 
    c[i] = sum[i] + i;          //处理 k[i] 
  }
  f[0] = 0;
  Hull[1].x = 0;
  Hull[1].y = 0;
  Hull[1].ad = 0;   //管他有没有必要的初始化 
  for (register unsigned i(1); i <= n; ++i) {
    while (l < r && (Hull[l + 1].y - Hull[l].y < ((b[i] * (Hull[l + 1].x - Hull[l].x)) << 1))) {
      ++l;  //将左端过气决策点 (斜率过小) 踢出凸壳 
    }
    f[i] = f[Hull[l].ad] + (b[i] - c[Hull[l].ad]) * (b[i] - c[Hull[l].ad]);
    now.x = c[i];
    now.y = c[i] * c[i] + f[i];     //转移 
    while (l < r && ((Hull[r].y - Hull[r - 1].y) * (now.x - Hull[r].x) > (Hull[r].x - Hull[r - 1].x) * (now.y - Hull[r].y))){
      --r;   //入队前维护下凸性 (单调性)
    }
    Hull[++r].x = now.x;
    Hull[r].y = now.y;
    Hull[r].ad = i;   //入队 
  }
  printf("%lld\n", f[n]);
  return Wild_Donkey;
}