租用游艇

GitHub跳转原题关系图返回列表

把出租站看成 DAG 上的点，按编号顺序做最短路/动态规划，转移到所有更下游的站点。

OJ: luogu

题目 ID: P1359

难度:普及-

标签:dp最短路动态规划

创建: 2026-06-19 11:10

更新: 2026-10-07 10:45

后置题目
luogu P4017最大食物链计数B 的转移复用了 A 教的「DAG 上按拓扑序沿有向边由前驱状态更新后继状态」这一步：A 靠编号天然拓扑序做 dp[j]=min(dp[j],dp[i]+cost)，B 显式 Kahn 拓扑排序后做 ways[v]+=ways[u]，仅把取 min 换成计数累加并补上生产者/消费者判定与取模。luogu P6145[USACO20FEB] Timeline GB 直接复用 A 教的『DAG 上沿无环顺序用 dp[u]+w 松弛后继 dp[v]』这一步：A 靠编号天然有序，B 换成 Kahn 拓扑序求顺序，再把 min 松弛改成长路 max 并加下界初值 S[i] 作为额外流程。luogu P3074[USACO13FEB] Milk Scheduling SB 的正式解法把 A 教的那一步「在 DAG 的有效点序上对每条出边做 dp[后继]=opt(dp[后继],dp[当前]+权值)」整步搬过来：A 里这个序就是天然编号顺序、取 min 求最少租金，B 用 Kahn 求出拓扑序、取 max 求最长依赖链，新增的只是求序手段。luogu P1796汤姆斯的天堂梦B 直接复用 A 教的『边单向即 DAG，于是按序用 dp[前驱]+边权 更新后继』这步（main.cpp:36 的 min(cur[planet], prev[from]+cost)），只是把 A 的编号序前驱换成输入给出的上一层前驱，并额外处理负权、变长输入与滚动数组。luogu P2196[NOIP 1996 提高组] 挖地雷B 直接复用 A 教的『编号即拓扑序、按编号从小到大枚举点对做 DAG 线性转移』这一步（连 O(n^2) 的 i<j 双层循环骨架都相同），只在最短路/自选起点的 min(dp[i]+cost) 上叠加点权最长路、f[i]=a[i] 边界与 pre[] 路径还原，属于加信息、换目标的台阶式叠加。luogu P1807最长路A 教过的“编号顺序即天然拓扑序”这一关键观察被 B 直接复用为 DAG 最长路的松弛顺序，B 只是把 min 松弛换成 max 并加上不可达哨兵；难度 普及- -> 普及/提高-

目录

  1. 题意
  2. 思路
    1. 代码
    2. 复杂度
    3. 总结
    4. 一图流解析

    题意

    有 n 个游艇站点。

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

    要求求出从 1 号站到 n 号站的最少租金。

    思路

    最直接的教学版做法是搜索所有可能的租船路线：

    cpp
    // 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 公式

    设 dpidp_i 表示从码头 11 到码头 ii 的最少租金。初始化：

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

    若可以从 ii 直接租船到 jj，费用为 costi,jcost_{i,j}，则：

    dpj=min⁡(dpj, dpi+costi,j) dp_j=\min(dp_j,\ dp_i+cost_{i,j})

    最终答案为：

    dpn dp_n

    公式解释：dp_i 保存已经到达码头 i 的最小费用。若再租一段从 i 到 j 的船，就能用 dp_i + cost_{i,j} 更新 dp_j；码头编号天然从小到大，形成无环转移。

    代码

    cpp
    #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(n2)O(n^2)
    • 空间复杂度：O(n2)O(n^2)

    总结

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

    一图流解析

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

    一图流解析