【.旅行.】

旅行

题目链接

题意

计算在给定的每天行驶的最小距离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;
}
 

总结

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