caioj 1082 动态规划入门（非常规DP6：火车票）-白红宇的个人博客

caioj 1082 动态规划入门（非常规DP6：火车票）

发布日期：2021-05-20 02:40:34 浏览次数：20 分类：精选文章

本文共 1547 字，大约阅读时间需要 5 分钟。

问题分析与解决方案

我们需要解决从起点到各车站的最小费用问题，可以使用动态规划来实现。该问题的关键在于找到从起点到每个车站的最优路径。

动态规划的方法

问题定义

设 f[i] 表示从起点到第 i 个车站的最小费用。我们需要找到每个车站的最少费用。

动态规划的递推关系

对于每个车站 i，我们有： [ f[i] = \min(f[j] + \text{dist}(j, i)) \quad \text{其中} \quad j < i ] 这表示从车站 j 到车站 i 的最小费用，加上 j 到 i 的间距，找到最小的总费用。

初始化

已知起点为 0，所以 f[0] = 0。其他车站的费用初始化为一个很大的数（例如 2e9）。

代码实现

#include 
   
    
#include 
    
     
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
typedef long long ll;
const int MAXN = 112;
ll a[MAXN], l[4], c[4], f[MAXN];
int n, s, e;
ll dist(ll n, ll m) {
    ll x = a[m] - a[n];
    if (0 <= x && x <= l[1]) return c[1];
    if (l[1] < x && x <= l[2]) return c[2];
    if (l[2] < x && x <= l[3]) return c[3];
    return 2e9;
}
int main() {
    REP(i, 1, 4) scanf("%lld", &l[i]);
    REP(i, 1, 4) scanf("%lld", &c[i]);
    scanf("%d%d%d", &n, &s, &e);
    if (s > e) swap(s, e);
    REP(i, 2, n+1) {
        scanf("%d", &a[i]);
        f[i] = 2e9;
    }
    f[s] = 0;
    REP(i, s, e+1) {
        REP(j, s, i) {
            if (f[i] > f[j] + dist(j, i)) {
                f[i] = f[j] + dist(j, i);
            }
        }
    }
    printf("%lld\n", f[e]);
    return 0;
}

代码解释

输入处理

读取路线距离参数 l 和费用 c，然后读取车站数 n，起点 s 和终点 e。

数组初始化

将所有车站的费用初始化为 2e9，表示初始状态下没有可行路径。起点 s 的费用设为 0。

动态规划计算

使用双指针技术，外层循环遍历每个车站 i，内层循环遍历所有可能的前驱车站 j。

计算从 j 到 i 的距离，使用自定义函数 dist。

比较当前 i 转 j 的路径费用，更新最小费用 f[i]。

结果输出

打印终点 e 的最小费用。

性能分析

时间复杂度

该算法的时间复杂度为 O(n^2)，适用于 n 较小的车站数量（例如 n = 112）。

空间复杂度

代码中使用的空间复杂度为 O(n)，主要用于存储车站间距离和费用数据。

结论

通过动态规划，我们可以高效地计算从起点到各个车站的最小费用。该算法通过逐步比较所有可能路径，找到最优解，确保了结果的正确性。

上一篇：洛谷 P1020 导弹拦截（LIS）

下一篇：caioj 1081 动态规划入门（非常规DP5：观光游览）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！