租用游艇

题意

有 n 个游艇站点。

可以从任意站点 i 直接租到任意更下游的站点 j，费用为 r[i][j]。

要求求出从 1 号站到 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// brute.cpp：搜索所有从 1 号站到 n 号站的租船方案，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const int INF = 1e9;

int n;
int cost_days[MAXN][MAXN];
int ans = INF;

void dfs(int x, int sum) {
    if (sum >= ans) {
        return;
    }
    if (x == n) {
        ans = min(ans, sum);
        return;
    }

    for (int y = x + 1; y <= n; y++) {
        dfs(y, sum + cost_days[x][y]);
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> cost_days[i][j];
        }
    }

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

但这题其实可以直接做 DP。

把每个站点看成一个点，从 i 向所有 j > i 连边，边权是租金。

由于边只会从小编号走向大编号，所以这是一张 DAG。

设 dp[i] 表示从 1 到 i 的最少租金，那么：

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

按编号顺序从小到大转移就行。

DP 公式

设 $dp_i$ 表示从码头 $1$ 到码头 $i$ 的最少租金。初始化：

dp_1=0,\quad dp_i=+\infty\ (i>1)

若可以从 $i$ 直接租船到 $j$ ，费用为 $cost_{i,j}$ ，则：

dp_j=\min(dp_j,\ dp_i+cost_{i,j})

最终答案为：

dp_n

公式解释：dp_i 保存已经到达码头 i 的最小费用。若再租一段从 i 到 j 的船，就能用 dp_i + cost_{i,j} 更新 dp_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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const int INF = 1e9;

int n;
int cost_days[MAXN][MAXN];
int dp[MAXN]; // dp[i]：从 1 号站到 i 号站的最少租金

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> cost_days[i][j];
        }
    }

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

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            dp[j] = min(dp[j], dp[i] + cost_days[i][j]);
        }
    }

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

复杂度

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

总结

这题虽然看起来像图论题，但因为图本身就是按编号单向向下的，所以直接按编号做 DP 最简单。

一图流解析

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

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析