[蓝桥杯 2015 国 B] 居民集会

题意

公路上有 n 户家庭，第 i 户在位置 d_i，人数是 t_i。

要设置 4 个集会点：

p1, p2, p3 在公路中间
p4 = L 固定在公路终点

并满足：

p1 <= p2 <= p3 <= p4

每户家庭只能向右走，去参加离自己最近且不在左边的那个集会点。

某户家庭的总代价是：

人数 * 行走距离

要求总开销最小。

思路

先看一个适合小数据验证的朴素 DP：

cpp

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
55
56
57
58
59
60
61
62
63
64
65
66#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const long long INF = (1LL << 60);

int n, L;
int d[MAXN];
int t[MAXN];
long long pre_w[MAXN];
long long pre_dw[MAXN];
long long dp[5][MAXN];

long long seg_cost(int l, int r) {
    if (l > r) {
        return 0;
    }
    long long sum_w = pre_w[r] - pre_w[l - 1];
    long long sum_dw = pre_dw[r] - pre_dw[l - 1];
    return 1LL * d[r] * sum_w - sum_dw;
}

long long last_cost(int l) {
    if (l > n) {
        return 0;
    }
    long long sum_w = pre_w[n] - pre_w[l - 1];
    long long sum_dw = pre_dw[n] - pre_dw[l - 1];
    return 1LL * L * sum_w - sum_dw;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：按“前 i 户用了 k 个中间会场”的朴素 DP。
    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> t[i];
        pre_w[i] = pre_w[i - 1] + t[i];
        pre_dw[i] = pre_dw[i - 1] + 1LL * d[i] * t[i];
    }

    for (int k = 0; k <= 3; k++) {
        for (int i = 0; i <= n; i++) {
            dp[k][i] = INF;
        }
    }
    dp[0][0] = 0;

    long long ans = last_cost(1);
    for (int k = 1; k <= 3; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[k - 1][j] >= INF / 2) {
                    continue;
                }
                dp[k][i] = min(dp[k][i], dp[k - 1][j] + seg_cost(j + 1, i));
            }
            ans = min(ans, dp[k][i] + last_cost(i + 1));
        }
    }

    cout << ans << '\n';
    return 0;
}

因为所有家庭都只能向右走，所以一旦会场位置确定，每户家庭最终去的会场一定按顺序分成连续几段。

也就是说：

前一段去 p1
下一段去 p2
再下一段去 p3
最后一段去终点 L

所以本质上是把家庭分成 4 段。

如果某一段家庭 [l..r] 都去位置 d_r 这个会场，那么这段的总代价是：

sum( (d_r - d_i) * t_i )

用前缀和可以写成：

d_r * (sum t_i) - (sum d_i * t_i)

于是设：

dp[k][i] 表示前 i 户家庭已经用掉 k 个中间会场时的最小代价

这里 k = 0..3，终点 L 那个会场单独最后处理。

转移时：

dp[k][i] = min( dp[k-1][j] + cost(j+1, i) )

其中 j < i。

把 cost(j+1, i) 展开并整理：

dp[k][i] = d_i * pre_w[i] - pre_dw[i] + min( dp[k-1][j] + pre_dw[j] - d_i * pre_w[j] )

对固定的 j 来说，括号里的部分是一条关于 d_i 的直线：

(dp[k-1][j] + pre_dw[j]) - pre_w[j] * d_i

于是每一层 k 都可以做一次斜率优化。

最后，前 i 户用掉了 1 到 3 个中间会场后，剩下 [i+1..n] 这段全部去终点 L，把这部分代价再加上即可。

这就把原来的 $O(3n^2)$ 转移压成了 $O(3n)$ 。

代码

cpp

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long INF = (1LL << 62);

int n, L;
int d[MAXN];
int t[MAXN];
long long pre_w[MAXN];
long long pre_dw[MAXN];
long long dp_prev[MAXN], dp_cur[MAXN];
int que[MAXN];

// 把区间 [l..r] 的家庭都安排到 d[r] 这个会场，总代价是多少。
long long seg_cost(int l, int r) {
    if (l > r) {
        return 0;
    }
    long long sum_w = pre_w[r] - pre_w[l - 1];
    long long sum_dw = pre_dw[r] - pre_dw[l - 1];
    return 1LL * d[r] * sum_w - sum_dw;
}

// 把区间 [l..n] 的家庭都安排到终点 L，总代价是多少。
long long last_cost(int l) {
    if (l > n) {
        return 0;
    }
    long long sum_w = pre_w[n] - pre_w[l - 1];
    long long sum_dw = pre_dw[n] - pre_dw[l - 1];
    return 1LL * L * sum_w - sum_dw;
}

long long line_value(int j, int x) {
    return dp_prev[j] + pre_dw[j] - 1LL * x * pre_w[j];
}

bool is_bad(int a, int b, int c) {
    long long m1 = -pre_w[a];
    long long m2 = -pre_w[b];
    long long m3 = -pre_w[c];
    long long b1 = dp_prev[a] + pre_dw[a];
    long long b2 = dp_prev[b] + pre_dw[b];
    long long b3 = dp_prev[c] + pre_dw[c];

    return (__int128)(b2 - b1) * (m2 - m3) >= (__int128)(b3 - b2) * (m1 - m2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> t[i];
        pre_w[i] = pre_w[i - 1] + t[i];
        pre_dw[i] = pre_dw[i - 1] + 1LL * d[i] * t[i];
    }

    for (int i = 0; i <= n; i++) {
        dp_prev[i] = INF;
    }
    dp_prev[0] = 0;

    long long ans = last_cost(1);

    // 最多再额外放 3 个中间会场。
    for (int k = 1; k <= 3; k++) {
        for (int i = 0; i <= n; i++) {
            dp_cur[i] = INF;
        }

        int head = 1, tail = 0;
        if (dp_prev[0] < INF / 2) {
            que[++tail] = 0;
        }

        for (int i = 1; i <= n; i++) {
            // 当前层转移到 i 时，只能从 j < i 转过来，
            // 因此先查询，再把 j=i 加入队列供后面使用。
            while (head < tail && line_value(que[head], d[i]) >= line_value(que[head + 1], d[i])) {
                head++;
            }

            if (head <= tail) {
                dp_cur[i] = 1LL * d[i] * pre_w[i] - pre_dw[i] + line_value(que[head], d[i]);
            }

            if (dp_prev[i] < INF / 2) {
                while (head <= tail && pre_w[que[tail]] == pre_w[i]) {
                    if (dp_prev[que[tail]] + pre_dw[que[tail]] <= dp_prev[i] + pre_dw[i]) {
                        goto skip_insert;
                    }
                    tail--;
                }
                while (head < tail && is_bad(que[tail - 1], que[tail], i)) {
                    tail--;
                }
                que[++tail] = i;
            }
skip_insert:
            ;
        }

        for (int i = 1; i <= n; i++) {
            if (dp_cur[i] < INF / 2) {
                ans = min(ans, dp_cur[i] + last_cost(i + 1));
            }
        }

        for (int i = 0; i <= n; i++) {
            dp_prev[i] = dp_cur[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

这题的关键是先看出“只能向右走”意味着答案一定是按顺序分段。

一旦把问题变成“区间分段 DP”，再把区间代价整理成：

一个只和 i 有关的项
加上一条来自 j 的直线

斜率优化就很自然了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[蓝桥杯 2015 国 B] 居民集会

目录

题意

思路

代码

复杂度

总结

一图流解析