[USACO08MAR] River Crossing S

题意

有 N 头牛需要过河，船夫 FJ 必须一直在船上。

已知：

船夫单独过河要 M 分钟
如果一次带 k 头牛，那么总过河时间会按照题目给出的增量逐步变长
过完一趟之后，如果还有牛没过河，船夫还要再划回来

目标是把所有牛都运到对岸，并让总时间最小。

这张表把题意翻成了背包模型：

原题对象	背包含义
一次带 `k` 头牛过河	一个大小为 `k` 的物品
这一趟来回所花时间	物品代价
总共 `N` 头牛	背包容量

思路

先看最直接的暴力：

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

const long long INF = (1LL << 60);

int n, m;
vector<long long> trip_cost;
long long answer = INF;

// 暴力枚举每一趟运走多少头牛。
// 这个做法只适合小数据，但能直接对应题意。
void dfs(int remain, long long current_cost) {
    if (remain == 0) {
        // 最后一趟不需要返回，所以总成本要少算一次单独返回的时间。
        answer = min(answer, current_cost - m);
        return;
    }

    if (current_cost >= answer + m) {
        return;
    }

    for (int take = 1; take <= remain; take++) {
        dfs(remain - take, current_cost + trip_cost[take]);
    }
}

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

    cin >> n >> m;
    trip_cost.assign(n + 1, 0);

    long long prefix = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix += x;
        trip_cost[i] = 2LL * m + prefix;
    }

    dfs(n, 0);
    cout << answer << '\n';

    return 0;
}

brute.cpp 直接枚举每一趟运走多少头牛，再统计总时间。

这个做法正确，但复杂度很高，只适合小数据验证。

关键观察是：一次运 k 头牛的花费只和 k 有关，和这 k 头牛是谁无关。所以我们只需要关心“这一趟运了多少头牛”，不需要关心具体是哪几头。

于是先预处理：

trip_cost[k] 表示“带 k 头牛来回一趟”的总时间

这张表说明状态定义：

状态	含义
`dp[j]`	运走 `j` 头牛的最小总时间

对于每个分组大小 k：

它可以重复使用很多次，所以是完全背包
转移是 dp[j] = min(dp[j], dp[j - k] + trip_cost[k])

最后所有牛都运走后，最后一次不需要再返回，所以答案要再减去一次单独返回的时间 M。

DP 公式

设 $trip_k$ 表示一次运走 $k$ 头牛并返回的总时间， $dp_j$ 表示运走 $j$ 头牛的最小总时间。初始化：

dp_0=0

每种载牛数量 $k$ 可以重复使用，因此：

dp_j=\min(dp_j,\ dp_{j-k}+trip_k)

最后一次不需要返回，答案为：

dp_n-M

公式解释：把一次运走 k 头牛看成一个可重复使用的选择。dp_j 表示已经运走 j 头的最小总时间，最后一次不用返回，所以要减去一次返回时间。

代码

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

const long long INF = (1LL << 60);

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

    int n, m;
    cin >> n >> m;

    vector<long long> trip_cost(n + 1, 0);
    long long prefix = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix += x;
        // round_cost[i]：来回运输一组 i 头牛的总时间
        trip_cost[i] = 2LL * m + prefix;
    }

    // dp[j]：把 j 头牛运到对岸，当前考虑若干种分组方案时的最小总时间
    vector<long long> dp(n + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        // 分组大小为 i，可以重复使用，所以是完全背包。
        for (int j = i; j <= n; j++) {
            if (dp[j - i] == INF) continue;
            dp[j] = min(dp[j], dp[j - i] + trip_cost[i]);
        }
    }

    // 最后一次不需要返回，所以减去一个单独返回的时间 m。
    cout << dp[n] - m << '\n';

    return 0;
}

复杂度

时间复杂度： $O(N^2)$
空间复杂度： $O(N)$

总结

这题的关键不是“牛是谁”，而是“每一趟运走多少头牛”。

把“一趟运 k 头牛”的代价预处理出来后，就变成了标准的完全背包最小值问题：

物品大小是 k
物品代价是 trip_cost[k]
背包容量是 N
最后答案再减去一次返回时间 M

一图流解析

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