丝绸之路

题意

一共有 N+1 个城市，要从 0 号走到 N 号，一共要经过 N 段路。

一共有 M 天，每天可以：

休息，不动
前进一段，到下一个城市

如果第 j 天走第 i 段路，会消耗疲劳值 $D_i * C_j$ 。

要求在不超过 M 天内到达终点，并使总疲劳值最小。

思路

最直接的做法是暴力枚举每天到底休息还是前进。

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：小数据 DFS，枚举每天是休息还是前进。

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

int n, m;
long long d[MAXN];
long long c[MAXN];
long long ans;

void dfs(int day, int city, long long cost) {
    if (day > m) {
        if (city == n) {
            ans = min(ans, cost);
        }
        return;
    }

    // 今天休息。
    dfs(day + 1, city, cost);

    // 今天前进一段。
    if (city < n) {
        dfs(day + 1, city + 1, cost + d[city + 1] * c[day]);
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }

    ans = INF;
    dfs(1, 0, 0);

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

brute.cpp 会从第 1 天开始，递归尝试“今天休息”或“今天前进”，最后在所有能按时到达终点的方案里取最小值。

这个方法对小数据很好理解，但每天都有两种决策，复杂度大约是 $O(2^M)$ ，显然无法处理 $M = 1000$ 。

更合适的模型是二维 DP。

设：

dp[i][j] = 前 j 天结束后，已经走完前 i 段路的最小疲劳值

那么第 j 天只有两种选择：

休息
这时走完的路段数不变：
dp[i][j] <- dp[i][j-1]
前进
这时今天走的只能是第 i 段路，因此昨天必须刚好走完前 i-1 段：
dp[i][j] <- dp[i-1][j-1] + D_i * C_j

状态表

样例中：

距离：10, 25, 15
天气：50, 30, 15, 40, 30

下面这张表展示 dp[i][j] 的关键值：

已走段数 `i` \ 天数 `j`	1	2	3	4	5
0	0	0	0	0	0
1	500	300	150	150	150
2	inf	1250	675	675	600
3	inf	inf	2000	1275	1125

从表里可以看到：

第 1 天休息，保留 dp[0][1] = 0

DP 公式

设 $dp_{i,j}$ 表示前 $j$ 天结束后，已经走完前 $i$ 段路的最小疲劳值。初始化：

dp_{0,j}=0,\quad dp_{i,0}=+\infty\ (i>0)

第 $j$ 天可以休息，也可以走第 $i$ 段路：

dp_{i,j}=\min\left(dp_{i,j-1},\ dp_{i-1,j-1}+D_i\cdot C_j\right)

最终答案为：

dp_{n,m}

第 2 天走第一段，得到 300
第 3 天走第二段，得到 675
第 4 天休息
第 5 天走第三段，得到 1125

这正好对应样例最优方案。

公式解释：第 j 天面对第 i 段路时，可以选择休息，让状态沿用 dp_{i,j-1}；也可以在这一天走完第 i 段，从 dp_{i-1,j-1} 转移并增加当天疲劳值。

代码

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

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

int n, m;
long long d[MAXN];
long long c[MAXN];
long long dp[MAXN][MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }

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

    // 前 0 天走完 0 段路，疲劳值为 0。
    dp[0][0] = 0;

    for (int day = 1; day <= m; day++) {
        dp[0][day] = 0; // 还没出发时，可以一直休息。

        for (int city = 1; city <= n; city++) {
            // 选择 1：今天休息，不前进。
            dp[city][day] = min(dp[city][day], dp[city][day - 1]);

            // 选择 2：今天从 city-1 走到 city。
            if (dp[city - 1][day - 1] < INF / 2) {
                dp[city][day] = min(dp[city][day], dp[city - 1][day - 1] + d[city] * c[day]);
            }
        }
    }

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

复杂度

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

总结

这题的核心是把“前几天做了哪些决策”压缩成“前几天走完了前几段路”的状态。

一旦状态定义清楚，转移就只剩下“今天休息”和“今天前进”两种情况。

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析