出租车拼车

题意

有 N 位 OIer 要去比赛。

在比赛开始前会经过 K 辆出租车，第 i 辆车到达校门的时间是 T_i，还有 Z_i 个空位。每辆车如果上了人，就需要支付固定车费 D，并且上车的每个人还要额外支付等待这辆车的时间费用。

要求让所有人都赶到比赛，并使总花费最小。

思路

先看最朴素的做法：

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据 DFS 枚举每辆车上几个人，作为教学版和对拍基准。

const int INF = 1000000000;

int n, k, d, s;
int t[105], z[105];
int ans = INF;

void dfs(int idx, int sent, int cost) {
    if (cost >= ans) {
        return;
    }
    if (idx > k) {
        if (sent == n) {
            ans = min(ans, cost);
        }
        return;
    }

    // 这辆车不上人。
    dfs(idx + 1, sent, cost);

    // 这辆车上 x 个人。
    for (int x = 1; x <= z[idx] && sent + x <= n; x++) {
        dfs(idx + 1, sent + x, cost + d + x * t[idx]);
    }
}

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

    cin >> n >> k >> d >> s;
    for (int i = 1; i <= k; i++) {
        cin >> t[i] >> z[i];
    }

    dfs(1, 0, 0);
    cout << ans << '\n';
    return 0;
}

brute.cpp 的想法很直接：对每辆车枚举它上 0..Z_i 个人，然后递归处理下一辆车。

这个做法很贴近题意，但分支太多，只适合小数据对拍。

观察一辆车真正会影响什么：

已经送走了多少人
当前总费用是多少

至于到底是哪些人上了车，其实没有区别。

于是可以做 DP。

设：

dp[i][j] 表示前 i 辆车已经考虑完，恰好送走 j 个人时的最小费用

处理第 i 辆车时有两类选择：

这辆车不上人
dp[i][j] = min(dp[i][j], dp[i-1][j])
这辆车上 x 个人
其中 $1 <= x <= Z_i$

增加费用是：
- 固定车费 D
- 等待费 $x * T_i$
所以转移为：

dp[i][j+x] = min(dp[i][j+x], dp[i-1][j] + D + x * T_i)

状态表

这张表描述状态的含义：

状态	含义
`dp[i][j]`	前 `i` 辆车里，恰好送走 `j` 个人的最小费用

因为每辆车最多只剩 4 个座位，所以第三层枚举很小，这个 DP 可以轻松通过。

DP 公式

设 $dp_{i,j}$ 表示前 $i$ 辆车考虑完，恰好送走 $j$ 个人时的最小费用。不让第 $i$ 辆车载人时：

dp_{i,j}=\min(dp_{i,j},\ dp_{i-1,j})

若第 $i$ 辆车载 $x$ 个人， $1\leqslant x\leqslant Z_i$ ，则：

dp_{i,j+x}=\min(dp_{i,j+x},\ dp_{i-1,j}+D+xT_i)

最终答案为：

dp_{K,N}

公式解释：乘客彼此没有区别，所以状态只需记录已经送走的人数。每辆车要么不上人，要么上 x 个人；上人时支付一次固定车费和 x 份等待费。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int INF = 1000000000;

int n, k, d, s;
int t[MAXN], z[MAXN];
int dp[MAXN][MAXN]; // dp[i][j]：前 i 辆车已经送走 j 个人的最小花费

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

    cin >> n >> k >> d >> s;
    for (int i = 1; i <= k; i++) {
        cin >> t[i] >> z[i];
    }

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

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            if (dp[i - 1][j] == INF) {
                continue;
            }

            // 这辆车一个人也不上。
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);

            // 这辆车上 x 个人。
            for (int x = 1; x <= z[i] && j + x <= n; x++) {
                int cost = dp[i - 1][j] + d + x * t[i];
                dp[i][j + x] = min(dp[i][j + x], cost);
            }
        }
    }

    cout << dp[k][n] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(KN)$
空间复杂度： $O(KN)$

总结

这题的关键是看出“人是同质的”，状态里只需要记录已经送走了多少人。

一旦把每辆车当成一次“上 0…Z_i 个人”的选择，整题就是一个非常标准的小容量费用 DP。

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析