【.旅行.】

发布时间:2023年12月28日

旅行

题目链接

题意

计算在给定的每天行驶的最小距离A和最大距离B的约束下,从起点到终点7000千米的旅行方案数。旅行过程中,可以在沿途的汽车旅馆住宿,每天晚上不开车。题目给出了一个有序的汽车旅馆列表,以及可能新增的旅馆列表。需要计算的是在满足每天行驶距离限制的情况下,从起点出发到达终点的所有可能旅行方案的总数。

思路

  1. 初始化
  2. 动态规划
  3. 输出结果

坑点

  1. 数组边界、动态规划逻辑、不必要的排序、不完整的输出结果、输入处理和代码可读性

算法一:动态规划

时间复杂度

O(n)

实现步骤
  1. 初始化一个数组a来存储旅馆的距离,包括起点和新增的旅馆。从标准输入读取三个整数:A(每天至少行驶的距离)、B(每天最多行驶的距离)和N(新增的旅馆数量)。读取新增的旅馆距离,并存储在数组a中
  2. 初始化一个数组f来存储到达每个旅馆的方案数,f[0]设置为1,表示从起点到起点的方案数。使用两层循环来计算到达每个旅馆的方案数。外层循环遍历每个旅馆,内层循环遍历之前的旅馆,检查是否满足行驶距离的条件。如果满足条件,将之前旅馆的方案数累加到当前旅馆的方案数中。
  3. 输出到达最后一个旅馆的方案数,即f[N-1]
代码
#include <bits/stdc++.h>
using namespace std;
int a[100] = { 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000 }, A, B, N, f[100];
int main() {
    cin >> A >> B >> N;//输入每天至少行驶的距离、每天最多行驶的距离和新增的汽车旅馆数量
    for (int i = 0; i < N; i ++) cin >> a[14+i-N];//读取新增的汽车旅馆距离,并将其存储在数组a的末尾。
    N += 14;//将新增的旅馆数量加上初始的旅馆数量
    sort(a, a+N);
    f[0] = 1;//表示从起点到起点的方案数
    for (int i = 1; i < N; i ++)
        for (int j = 0; j < i; j ++)//遍历之前的旅馆,以计算到达当前旅馆的方案数
            if (a[i]-a[j] >= A && a[i]-a[j] <= B) f[i] += f[j];
            //计算到达每个旅馆的方案数
    cout << f[N-1] << endl;
    //输出到达最后一个旅馆的方案数
    return 0;
}
 

总结

需要使用动态规划的方法来计算到达每个旅馆的方案数。在这个过程中,需要定义动态规划的状态和状态转移方程,并初始化边界条件。最后,输出到达终点旅馆的方案数

文章来源:https://blog.csdn.net/pandawen123/article/details/135278322
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。