算法学习笔记(3):与斜率优化共舞

时间:2023-02-02 17:06:51

对于像如下这样的 dp 方程,我们可以使用斜率优化解决。

\[dp_i = \min / \max \{ a_i \times b_j + c_i + d_j \} \]


例题:P2900 Land Acquisition G

显然,如果 \(w_i \ge w_j\)\(l_i \ge l_j\),那么土地 \(j\) 可以直接被土地 \(i\) 并购。

考虑将所有土地按 \(w_i\) 降序排序,\(w_i\) 相同的按 \(l_i\) 降序排序,再通过双指针保留不能被其它土地并购的土地。

注意到此时被保留下的土地,\(w_i\) 满足 单调递减\(l_i\) 满足 单调递增

\(dp_i\) 表示将第 \(1 \sim i\) 块土地并购的最小代价,不难列出 dp 方程:

\[dp_i = \min_{0 \le j < i} \{ dp_j + w_{j + 1} \times l_{i} \} \]

上面的方程复杂度为 \(O(n^2)\),然而 \(n \leq 5 \times 10^4\),我们需要想办法优化。

先将 \(\min\) 去掉,再把 \(w_{j + 1} \times l_{i}\) 移到左边,得:

\[-w_{j + 1} \times l_i + dp_i = dp_j \]

将所有能够转移到 \(i\)\(j\) 视为一个点 \((-w_{j + 1}, dp_j)\),那么问题就转化成了:

  • 有一条斜率为 \(l_i\) 的直线,这条直线需要经过上述的这些点中的一个或多个,并且希望它的截距最小。

上面这句话有点抽象,不妨将 原方程 与 一次函数 做一个对比,发现它们确实十分相似:

\[\textcolor{red}{-w_{j + 1}} \times \textcolor{blue}{l_i} + \textcolor{green}{dp_i} = \textcolor{orange}{dp_j} \]

\[\newline \textcolor{red}{k}\textcolor{blue}{x} + \textcolor{green}{b} = \textcolor{orange}{y} \]

本质就是我们拿着一条斜率为 \(l_i\) 的直线,从下往上靠(增加它的截距),直到某一时刻这条线经过了我们维护的一个或多个点,停下来,此时截距(\(dp_i\))一定是最小的。

算法学习笔记(3):与斜率优化共舞

仔细观察可以发现,无论斜率 (\(l_i\)) 是多少,有些点一定不会被第一次经过(如下图灰色点)。将这些点去除,剩余的点恰好形成了一个右下凸壳:

算法学习笔记(3):与斜率优化共舞

不妨先来维护这个凸壳,假设现在加入点 \(C(-w_{i + 1}, dp_i)\),考虑凸壳上最新的两个点 \(A\)\(B\),只可能有以下两种情况:

  • \(C\) 点可以直接加入凸壳。

算法学习笔记(3):与斜率优化共舞

记点 \(X\) 与点 \(Y\) 所连成的直线斜率为 \(\text{slope}(X, Y)\),则 \(C\) 能直接加入凸壳当且仅当 \(\text{slope}(A, B) \leq \text{slope}(B, C)\)

  • \(C\) 点加入后无法形成凸壳。

算法学习笔记(3):与斜率优化共舞

这时候一定有 \(\text{slope}(A, B) \geq \text{slope}(B, C)\),故需要将 \(B\) 弹出凸壳,在拿剩余凸壳最新的两个点与 \(C\) 作比较。

由于这些点的 \(x\) 单调递增,可以使用类似单调栈的方法维护,时间复杂度 \(O(n)\)

接下来就是要在维护出的凸壳上找到最优决策点,随便画一张图,由于这些直线的斜率一定不断增加,所以最优决策点一定不断向凸壳上方移动:

算法学习笔记(3):与斜率优化共舞

进一步观察,可以发现,如果凸壳上相邻的两点 \(A\)\(B\) 满足 \(\text{slope}(A, B) \leq l_i\),那么点 \(B\) 永远在 \(i\) 以后一定 不会成为最优决策点。不妨把原来维护凸壳的单调栈换成单调队列,通过凸壳最前面两点的斜率判断是否弹出队头。最终,队头一定是当前的最优决策点。

时间复杂度 \(O(n)\)(本题由于要排序所以总复杂度应该为 \(O(n \log n)\),这里只计算了 dp 的复杂度)。代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, pos, q[50005], h, t;
long long dp[50005];
struct land
{
  int w, l;
  bool operator<(const land t) const
  {
    return w == t.w ? l > t.l : w > t.w;
  }
} p[50005];

double X(int j)
{
  return -p[j + 1].w;
}

double Y(int j)
{
  return dp[j];
}

double slope(int x, int y)
{
  return (Y(x) - Y(y)) / (X(x) - X(y));
}

int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d%d", &p[i].w, &p[i].l);
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; i++)
    if (p[i].l > p[pos].l)
      p[++pos] = p[i];
  for (int i = 1; i <= pos; i++)
  {
    while (h < t && slope(q[h], q[h + 1]) <= p[i].l)
      h++;
    dp[i] = dp[q[h]] + p[q[h] + 1].w * 1LL * p[i].l;
    while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i))
      t--;
    q[++t] = i;
  }
  printf("%lld", dp[pos]);
  return 0;
}

例题:P3195 玩具装箱

\(s_i = \sum_{j=1}^i C_i\),则可以列出 dp 方程:

\[dp_i = \min_{0 \le j < i} \{ dp_j + (s_i - s_j + i - j - 1 - L)^2 \} \]

\(a_i = s_i + i - 1 - L, b_i = s_j + j\),原方程变为

\[dp_i = \min_{0 \le j < i} \{ dp_j + (a_i - b_j)^2 \} \]

\[dp_i = \min_{0 \le j < i} \{ dp_j - 2a_ib_j + b_j^2 \} + a_i^2 \]

\(\min\) 及其以外得东西去掉,得

\[dp_i = dp_j - 2a_ib_j + b_j^2 \]

化为直线的形式

\[2a_ib_j + dp_i = dp_j + b_j^2 \]

类似与之前的形式,把每个 \(j\) 视作点 \((b_j, dp_j + b_j^2)\),每次直线的斜率为 \(2a_i\),做斜率优化即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, L, C, h, t, q[50005];
ll s[50005], dp[50005];

double X(int j)
{
  return s[j] + j;
}

double Y(int j)
{
  return (s[j] + j) * (s[j] + j) + dp[j];
}

double slope(int i, int j)
{
  return (Y(i) - Y(j)) / (X(i) - X(j));
}

int main()
{
  scanf("%d%d", &n, &L);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d", &C);
    s[i] = s[i - 1] + C;
  }
  h = t = 1;
  for (int i = 1; i <= n; i++)
  {
    while (h < t && slope(q[h], q[h + 1]) <= 2 * (s[i] + i - L - 1))
      h++;
    dp[i] = dp[q[h]] + sq(s[i] - s[q[h]] + i - q[h] - 1 - L);
    while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i))
      t--;
    q[++t] = i;
  }
  printf("%lld", dp[n]);
  return 0;
}

例题:P5785 任务安排(弱化版 P2365 任务安排

至于方程是如何提前计算贡献的我就不细说了,记 \(\text{sumT}_i = \sum_{j=1}^i T_i,\text{sumC}_i = \sum_{j=1}^i C_i\),可列出方程:

\[dp_i = \min \{ dp_j + \text{sumT}_i \times (\text{sumC}_i - \text{sumC}_j) + s \times (\text{sumC}_n - \text{sumC}_j) \} \]

展开整理成直线形式,即

\[(\text{sumT}_i + s) \times \text{sumC}_j + dp_i = dp_j \]

每个 \(j\) 所代表的点:\((\text{sumC}_i, dp_j)\),直线斜率 \(\text{sumT}_i + s\)

正准备敲板子的你突然发现了这一条限制:

\[|T_i| \leq 2^8 \]

也就是说

\[-2^8 \le T_i \le 2^8 \]

那么 \(\text{sumT}_i + s\) 就不单调了,就不能一味地弹出队头了!

可凸壳上相邻两点地斜率还是单调的啊!那么只需要在凸壳上二分,找决策点即可。

时间复杂度 \(O(n \log n)\)

#include <bits/stdc++.h>
using namespace std;
long long n, s, sumT[300005], sumC[300005], dp[300005], top, stk[300005];

long long X(int j)
{
  return sumC[j];
}

long long long Y(int j)
{
  return dp[j];
}

int main()
{
  scanf("%lld%lld", &n, &s);
  for (int i = 1; i <= n; i++)
  {
    long long t, f;
    scanf("%lld%lld", &t, &f);
    sumT[i] = sumT[i - 1] + t;
    sumC[i] = sumC[i - 1] + f;
  }
  stk[++top] = 0;
  for (int i = 1; i <= n; i++)
  {
    int l = 1, r = top - 1, pos = stk[top];
    while (l <= r)
    {
      int mid = (l + r) >> 1;
      if (Y(stk[mid + 1]) - Y(stk[mid]) > (sumT[i] + s) * (X(stk[mid + 1]) - X(stk[mid])))
        pos = stk[mid], r = mid - 1;
      else
        l = mid + 1;
    }
    dp[i] = dp[pos] + sumT[i] * (sumC[i] - sumC[pos]) + s * (sumC[n] - sumC[pos]);
    while (top > 1 && (Y(stk[top]) - Y(stk[top - 1])) * (X(i) - X(stk[top])) >= (Y(i) - Y(stk[top])) * (X(stk[top]) - X(stk[top - 1])))
      top--;
    stk[++top] = i;
  }
  printf("%lld", dp[n]);
  return 0;
}

注:斜率优化比较时建议移项,把除法化为乘法;如果使用 double 类型的 slope 很可能会产生精度误差(本题就卡了。


斜率优化小结:

  • 列出方程,先通过一些简单的代换化简成直线形式。

  • 通过 \(\min / \max\) 以及 \(X\)\(Y\) 坐标的单调性判断凸壳方向。

  • 如果直线斜率不单调,使用二分维护。

  • 如果 \(Y\) 坐标不单调,可以证明对最终凸壳没有影响。

  • 如果 \(X\) 坐标不单调,可以考虑 \(\text{CDQ}\) 分治解决,时间复杂度 \(O(n \log^2 n)\)