「洛谷 P4341」锯木厂选址 - 斜率优化 DP

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

从山顶上到山底下沿着一条直线种植了 \(n\) 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。

木材只能朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建这两个锯木厂，使得运输的费用总和最小。假定运输每公斤木材每米需要一分钱。

你的任务是编写一个程序，从输入文件中读入树的个数和他们的重量与位置，计算最小运输费用。

数据范围：\(n \le 20000\)。

解题思路

模型建立

首先我们解决 DP 问题。设第 \(i\) 颗树的重量为 \(w_i\), \(i\) 到 \(i + 1\) 的距离为 \(d_i\)。我们可以设 \(f_{i, j}\) 表示只考虑前 \(j\) 颗树的情况下，已经有 \(i\) 个锯木厂，且第 \(j\) 个位置为锯木厂的最小运输费用。于是我们可以得出下列转移方程：

\[ f_{i + 1, k} = \min\{ f_{i + 1, k}, f_{i, j} + \sum_{l = i + 1}^{k - 1}(d_i \sum_{m = i + 1}^{l}w_m) \} \quad k \in (i, n + 1] \]

初始化为 \(f_{i, j} = \begin{cases} 0 & i = 0 \wedge j = 0 \\ +\infty & otherwise. \end{cases}\)，答案显然为 \(f_{3, n + 1}\)。

化简

显然这个方程有许多地方都可以优化。我们首先可以将方程中的求和符号化掉。我们可以预处理 \(w\) 的前缀和 \(\text{sw}\)、\(d\) 的前缀和 \(\text{sd}\) 和 \(\text{sw} \times d\) 的前缀和 \(\text{md}\)。即 \(\text{sw}_n = \sum_{i = 1}^{n} w_i\)、\(\text{sd}_n = \sum_{i = 1}^{n} d_i\)、\(\text{md}_n = \sum_{i = 1}^{n}(\text{sw}_i \times d_i)\)。于是经过一系列数学变化，我们可以将方程化成下列形式。

\[ f_{i + 1, k} = \min\{ f_{i + 1, k}, f_{i, j} + (\text{md}_{k - 1} - \text{md}_{j - 1}) - \text{sw}_j \times (\text{sd}_{k - 1} - \text{sd}_{j - 1}) \} \quad k \in (i, n + 1] \]

接下来我们将方程换一下参，得出下列方程：

\[ f_{i, j} = \min\limits_{0 \le k < j} \{ f_{i - 1, k} + (\text{md}_{j - 1} - \text{md}_{k - 1}) - \text{sw}_k \times (\text{sd}_{j - 1} - \text{sd}_{k - 1}) \} \]

然后对于 \(f_{i, j}\) 的第一维，我们可以将 \(g_{j}\) 赋值为 \(f_{i - 1, j}\)，然后将方程中的 \(f_{i - 1, j}\) 替换掉。这样即可实现类似于滚动数组的模式。于是可将 \(f\) 转化为一维。计算答案时只需重复计算三次 \(f\)，每次计算完成后将 \(f\) 复制到 \(g\)，再清空 \(f\) 即可。可得到下列方程：

\[ f_i = \min\limits_{0 \le j < i} \{ g_j + (\text{md}_{i - 1} - \text{md}_{j - 1}) - \text{sw}_j (\text{sd}_{i - 1} - \text{sd}_{j - 1}) \} \]

斜率优化

显然 \(\exists j \in (i, n + 1]\)，满足下列方程：

\[ f_i = g_j + (\text{md}_{i - 1} - \text{md}_{j - 1}) - \text{sw}_j (\text{sd}_{i - 1} - \text{sd}_{j - 1}) \]

经过拆括号和移项，可得到下列方程：

\[ g_j - \text{md}_{j - 1} - \text{sw}_j\text{sd}_{j - 1} = \text{sd}_{i - 1}\text{sw}_j + f_i - \text{md}_{i - 1} \]

于是我们可将其看作以 \(\text{sd}_{i - 1}\) 为斜率，以 \(f_i - \text{md}_{i - 1}\) 为截距，以 \(\text{sw}_j\) 为自变量、以 \(g_j - \text{md}_{j - 1} - \text{sw}_j\text{sd}_{j - 1}\) 为因变量的一次函数。由于斜率和去掉 \(f_i\) 的截距均为常数，于是我们可以进行斜率优化，即最小化截距以解决问题。

于是我们需要维护每个点。而对于相邻的点 \(x < y\)，当且仅当满足下列不等式时，\(y\) 比 \(x\) 优：

\[ \begin{align*} g_x + (\text{md}_{i - 1} - \text{md}_{x - 1}) - \text{sw}_x (\text{sd}_{i - 1} - \text{sd}_{x - 1}) &> \\ g_y + (\text{md}_{i - 1} - \text{md}_{y - 1}) - \text{sw}_y (\text{sd}_{i - 1} - \text{sd}_{y - 1}) & \end{align*} \]

经过化简可变化为：

\[ \frac{(g_x - \text{md}_{x - 1} + \text{sw}_x\text{sd}_{x - 1}) - (g_y - \text{md}_{y - 1} + \text{sw}_y\text{sd}_{y - 1})}{\text{sw}_x - \text{sw}_y} < \text{sd}_{i - 1} \]

于是我们可以定义相邻 \(x < y\) 两点斜率为 \(\text{slope}(x, y) = \frac{(g_x - \text{md}_{x - 1} + \text{sw}_x\text{sd}_{x - 1}) - (g_y - \text{md}_{y - 1} + \text{sw}_y\text{sd}_{y - 1})}{\text{sw}_x - \text{sw}_y}\)。我们只需要通过维护一个单调队列来维护这些点。每次取队首的时候就将队首的斜率 \(\text{slope}(q_l, q_{l + 1})\)与 \(\text{sd}_{i - 1}\) 比较，弹出不够优的点。每次插入新点的时候就比较队尾的斜率 \(\text{slope}(q_{r - 1}, q_r)\) 和 \(\text{slope}(q_r, i)\)。通过画图以及几何知识得知当 \(\text{slope}(q_{r - 1}, q_r) >\text{slope}(q_r, i)\) 时，\(i\) 比 \(q_r\) 优，弹出不够优的点即可。

最后每次取单调队列队首即为 \(f_i\) 的最优答案。编写程序的时候注意一下边界处理即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>

int main() {
    int n;
    scanf("%d", &n);

    std::vector<long long> w(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld %lld", &w[i], &d[i]);

    std::vector<long long> sw(n + 1), sd(n + 1), md(n + 1);
    for (int i = 1; i <= n; i++) {
        sw[i] = sw[i - 1] + w[i];
        sd[i] = sd[i - 1] + d[i];
        md[i] = md[i - 1] + sw[i] * d[i];
    }

    std::vector<long long> f(n + 2, LLONG_MAX), g(n + 2, LLONG_MAX);
    f[0] = 0;

    auto slope = [&](int x, int y) {
        return 1.0 * ((g[x] - (x - 1 < 0 ? 0 : md[x - 1]) + sw[x] * (x - 1 < 0 ? 0 : sd[x - 1])) -
                      (g[y] - (y - 1 < 0 ? 0 : md[y - 1]) + sw[y] * (y - 1 < 0 ? 0 : sd[y - 1]))) / 
                     (sw[x] - sw[y]);
    };

    for (int _ = 1; _ <= 3; _++) {
        g = f;
        std::fill(f.begin(), f.end(), LLONG_MAX);
        f[0] = 0;

        std::vector<int> q(n + 2);
        auto l = q.begin(), r = q.begin();
        q[0] = 0;

        for (int i = 1; i <= n + 1; i++) {
            while (l < r && slope(*(l), *(l + 1)) < sd[i - 1]) l++;

            int &j = *l;
            f[i] = g[j] + (md[i - 1] - (j - 1 < 0 ? 0 : md[j - 1])) - sw[j] * (sd[i - 1] - (j - 1 < 0 ? 0 : sd[j - 1]));

            if (g[i] != LLONG_MAX) {
                while (l < r && slope(*(r - 1), *r) > slope(*r, i)) r--;
                *(++r) = i;
            }
        }
    }

    printf("%lld\n", f[n + 1]);

    return 0;
}