题目描述

一只蜗牛从二维坐标系的原点 $(0,0)$ 出发，目标是到达第 $n$ 根竹竿的底部 $(x_n, 0)$。
共有 $n$ 根无限高的竹竿竖立在 $x$ 轴上，第 $i$ 根竹竿位于横坐标 $x_i$ 处 ($x_1 < x_2 < \dots < x_n$)。

蜗牛的移动方式和速度如下：
1. 在 $x$ 轴上爬行：速度为 1.0 单位/秒。
2. 在竹竿上向上爬行：速度为 0.7 单位/秒。
3. 在竹竿上向下爬行：速度为 1.3 单位/秒。
4. 瞬移（可选）：对于 $0 < i < n$，存在一个传送门。如果蜗牛位于第 $i$ 根竹竿的高度 $a_i$ 处（即点 $(x_i, a_i)$），它可以瞬间移动到第 $i+1$ 根竹竿的高度 $b_{i+1}$ 处（即点 $(x_{i+1}, b_{i+1})$）。

蜗牛只能在 $x$ 轴或竹竿上移动。计算蜗牛从 $(0,0)$ 到达 $(x_n, 0)$ 所需的最短时间。

样例

输入:
3
1 10 11
1 1
2 1

输出:

4.20

样例解释:
最优路线：
1. $(0,0) \to (1,0)$: 沿 x 轴爬行，距离 1，时间 $1 / 1.0 = 1$。
2. $(1,0) \to (1,1)$: 沿第 1 根竹竿向上爬行，距离 1，时间 $1 / 0.7 \approx 1.4286$。（到达传送点）
3. $(1,1) \to (10,1)$: 使用第 1 根到第 2 根的传送门，瞬移。时间 0。
4. $(10,1) \to (10,0)$: 沿第 2 根竹竿向下爬行，距离 1，时间 $1 / 1.3 \approx 0.7692$。
5. $(10,0) \to (11,0)$: 沿 x 轴爬行，距离 1，时间 $1 / 1.0 = 1$。
总时间 $\approx 1 + 1.4286 + 0 + 0.7692 + 1 = 4.1978$。四舍五入保留两位小数为 4.20。

算法 (动态规划)

$O(N)$

思路分析

1. 问题性质: 这是一个求解最短时间的问题，路径是按顺序从竹竿 $i$ 到竹竿 $i+1$ 进行的。这符合动态规划 (DP) 的模式。我们需要定义状态来表示到达某个阶段（某个竹竿）的最小耗时。

2. 状态定义: 当蜗牛到达第 $i$ 根竹竿时，它可能处于两种关键位置，这两种位置会影响后续的决策：

   • 在竹竿的底部 $(x_i, 0)$。
   • 在竹竿的传送门出发点 $(x_i, a_i)$（对于 $i < n$）。
     我们定义 DP 状态如下（使用 1-based 索引对应竹竿编号）：
   • dp[i][0]：到达第 $i$ 根竹竿底部 $(x_i, 0)$ 的最小时间。
   • dp[i][1]：到达第 $i$ 根竹竿的传送门出发点 $(x_i, a_i)$ 的最小时间。

3. 状态转移: 我们需要计算如何从第 $i-1$ 根竹竿的状态转移到第 $i$ 根竹竿的状态。

   • 计算 dp[i][0] (到达第 $i$ 根竹竿底部):
     有两种主要方式可以到达 $(x_i, 0)$：

     1. 从第 $i-1$ 根竹竿底部走过来: 先到达 $(x_{i-1}, 0)$ (最小时间 dp[i-1][0])，然后沿 $x$ 轴走到 $(x_i, 0)$。水平移动时间为 $(x_i - x_{i-1}) / 1.0 = x_i - x_{i-1}$。总时间为 $dp[i-1][0] + x_i - x_{i-1}$。
     2. 从第 $i-1$ 根竹竿传送过来，然后爬下来: 先到达第 $i-1$ 根竹竿的传送点 $(x_{i-1}, a_{i-1})$ (最小时间 dp[i-1][1])。然后使用传送门瞬间到达第 $i$ 根竹竿的 $(x_i, b_i)$ 位置。（注意：根据代码实现和输入格式，从 $i-1$ 传送到 $i$ 的参数似乎用 a[i-1] 和 b[i-1] 表示，其中 b[i-1] 是在第 $i$ 根竹竿的到达高度）。从 $(x_i, b_i)$ 爬到 $(x_i, 0)$ 的时间为 $b_i / 1.3$。总时间为 $dp[i-1][1] + b_i / 1.3$。（这里的 b_i 对应代码中的 b[i-1]）。
        取这两种方式的最小值：
        $$dp[i][0] = \min( dp[i-1][0] + x_i - x_{i-1}, \quad dp[i-1][1] + \frac{b_{i}}{1.3} )$$
        (参照代码，应为 $dp[i][0] = \min( dp[i-1][0] + x_i - x_{i-1}, \quad dp[i-1][1] + \frac{b[i-1]}{1.3} )$)

   • 计算 dp[i][1] (到达第 $i$ 根竹竿的传送点):
     有两种主要方式可以到达 $(x_i, a_i)$：

     1. 先到达第 $i$ 根竹竿底部，然后爬上去: 先到达 $(x_i, 0)$ (最小时间 dp[i][0])，然后向上爬到 $(x_i, a_i)$。爬升时间为 $a_i / 0.7$。总时间为 $dp[i][0] + a_i / 0.7$。
     2. 从第 $i-1$ 根竹竿传送过来，然后爬上/爬下: 先到达第 $i-1$ 根竹竿的传送点 $(x_{i-1}, a_{i-1})$ (最小时间 dp[i-1][1])。然后使用传送门瞬间到达第 $i$ 根竹竿的 $(x_i, b_i)$ 位置。从 $(x_i, b_i)$ 爬到 $(x_i, a_i)$ 的时间取决于 $b_i$ 和 $a_i$ 的相对大小：
        • 如果 $b_i \ge a_i$，向下爬，时间为 $(b_i - a_i) / 1.3$。
        • 如果 $b_i < a_i$，向上爬，时间为 $(a_i - b_i) / 0.7$。
          可以统一写成 $\frac{|b_i - a_i|}{\text{速度}}$，其中速度根据方向决定。
          总时间为 $dp[i-1][1] + \frac{|b_i - a_i|}{(b_i \ge a_i ? 1.3 : 0.7)}$。（这里的 $b_i$ 对应代码中的 b[i-1]）。
          取这两种方式的最小值：
          $$dp[i][1] = \min\left( dp[i][0] + \frac{a_i}{0.7}, \quad dp[i-1][1] + \frac{|b_i - a_i|}{(b_i \ge a_i ? 1.3 : 0.7)} \right)$$
          (参照代码，应为 $dp[i][1] = \min\left( dp[i][0] + \frac{a[i]}{0.7}, \quad dp[i-1][1] + \frac{|b[i-1] - a[i]|}{(b[i-1] \ge a[i] ? 1.3 : 0.7)} \right)$)

4. 基础情况 (Base Case):
   计算到达第一根竹竿 (i=1) 的状态。

   • dp[1][0]：从原点 $(0,0)$ 到 $(x_1, 0)$，只能沿 $x$ 轴走。时间为 $x_1 / 1.0 = x_1$。
   • dp[1][1]：从原点 $(0,0)$ 到 $(x_1, 0)$，再爬升到 $(x_1, a_1)$。时间为 $x_1 / 1.0 + a_1 / 0.7 = x_1 + a_1 / 0.7$。

5. 最终答案:
   目标是到达第 $n$ 根竹竿的底部 $(x_n, 0)$。所以最终答案是 dp[n][0]。

6. 实现细节:

   • 使用 double 类型存储时间，因为速度不是整数。
   • 初始化 DP 数组为一个非常大的值（表示无穷大），例如代码中的 inf = 1e9（对于 double 类型，可以使用 numeric_limits<double>::infinity()）。
   • 数组索引：代码使用了 1-based 索引 for dp 和 x (大小 n+1)，但 a 和 b 数组似乎也是 1-based (大小 n)，并且在访问时使用了 i-1 的索引，这需要注意。
     • x[i] 存储第 i 根竹竿的横坐标 ($1 \le i \le n$)。
     • a[i] 和 b[i] 在代码中 for (int i = 1; i < n; i ++ ) { cin >> a[i] >> b[i]; } 读入。这意味着 a[i] 是第 $i$ 根竹竿的传送出发高度，b[i] 是第 $i+1$ 根竹竿的传送到达高度。
     • 因此，在计算 dp[i] 时，涉及到的传送参数是 a[i-1] (从 $i-1$ 出发的高度) 和 b[i-1] (到达 $i$ 的高度)。
   • 输出格式要求保留两位小数，使用 fixed 和 setprecision(2)。

时间复杂度

• DP 状态数为 $2N$。
• 每个状态的计算依赖于前一个状态的两个值，计算时间为 $O(1)$。
• 总的时间复杂度为 O(N)。

空间复杂度

• 需要存储 $x, a, b$ 数组，大小为 $O(N)$。
• 需要存储 DP 数组，大小为 $O(N)$。
• 总空间复杂度为 O(N)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long (本题主要用 double)

constexpr double inf = 1e18; // 定义一个足够大的 double 值表示无穷大

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 竹竿数量
    cin >> n;

    // x[i]: 第 i 根竹竿的横坐标 (1-based index)
    vector<int> x(n + 1);
    for (int i = 1; i <= n; i ++ ) {
        cin >> x[i];
    }

    // a[i]: 第 i 根竹竿的传送出发高度 (1 <= i < n)
    // b[i]: 第 i+1 根竹竿的传送到达高度 (1 <= i < n)
    // 使用大小为 n 的数组，索引 1 到 n-1 有效
    vector<int> a(n), b(n); 
    for (int i = 1; i < n; i ++ ) {
        cin >> a[i] >> b[i];
    }

    // dp[i][0]: 到达第 i 根竹竿底部 (x_i, 0) 的最小时间
    // dp[i][1]: 到达第 i 根竹竿传送点 (x_i, a_i) 的最小时间
    vector dp(n + 1, vector<double>(2, inf)); // 初始化为无穷大

    // Base Case: 到达第一根竹竿
    dp[1][0] = x[1]; // 从 (0,0) 到 (x1, 0) 时间为 x1
    // 注意：如果 n=1，则不需要 a[1]。需要处理边界。
    // 但题目保证 n>=1，且传送门只在 i < n 时存在。
    // a[1] 是有效的，因为用于从 pole 1 传送到 pole 2。
    if (n > 1) { // 只有当有后续竹竿时，计算到达传送点才有意义
       dp[1][1] = (double)x[1] + (double)a[1] / 0.7; // 到 (x1, 0) 再爬升到 a1
    } else {
       // 如果 n=1，目标就是 dp[1][0]，dp[1][1] 不会被用到
       dp[1][1] = inf; // 或者保持 inf
    }


    // DP 递推: 计算 i 从 2 到 n
    for (int i = 2; i <= n; i ++ ) {
        // --- 计算 dp[i][0] ---
        // 方式1: 从 dp[i-1][0] 走过来
        dp[i][0] = dp[i - 1][0] + (x[i] - x[i - 1]); 
        // 方式2: 从 dp[i-1][1] 传送过来再爬下来 (到达高度是 b[i-1])
        dp[i][0] = min(dp[i][0], dp[i - 1][1] + (double)b[i - 1] / 1.3);

        // --- 计算 dp[i][1] ---
        // 方式1: 从 dp[i][0] 爬上去 (目标高度 a[i])
        // 注意: a[n] 未定义，但如果 i=n，dp[n][1] 实际上不会被用到最终结果 dp[n][0]
        // 为了代码简洁性，这里计算了 dp[n][1]，但它不会影响最终答案。
        // 需要确保 a[n] 访问安全，或者在 i=n 时不计算 dp[i][1]。
        // 如果假设 a[n] 需要被访问，可以认为 a[n]=0 或处理。
        // 更好的做法是循环到 n-1 计算 dp[n][0] 所需的 dp[n-1]，然后单独计算 dp[n][0]。
        // 或者，保证 a 数组大小为 n+1 或在使用 a[i] 前检查 i < n。
        // 当前代码访问了 a[n] (如果 i=n)。假设 vector a 大小为 n，访问 a[n] 是越界的。
        // 修正：应该只在 i < n 时计算 dp[i][1] 的传送部分，或者调整 a 的大小/逻辑。
        // 我们按照代码逻辑来解释，假设 a[n] 可以访问且有意义（例如为 0）。
        // 更好的方法是在 i=n 时特殊处理 dp[n][1] 或根本不计算它。
        // 然而，由于最终答案是 dp[n][0]，且 dp[n][0] 只依赖 dp[n-1][...]，所以计算 dp[n][1] 没影响结果。
        // 假定 a[n] 存在且被访问
        if (i <= n) { // 理论上 dp[n][1] 无需计算，但按代码逻辑写
             double climb_up_cost = (i == n) ? inf : (double)a[i] / 0.7; // 假设无法爬到 a[n]
             if (i < n) dp[i][1] = dp[i][0] + climb_up_cost;
             else dp[i][1] = inf; // 无法到达虚构的 a[n] 除非在底部

             // 方式2: 从 dp[i-1][1] 传送过来再爬 (到达高度 b[i-1]，目标高度 a[i])
             double climb_teleport_cost = abs((double)b[i-1] - (i < n ? a[i] : 0.0)); // 到 a[i] 或如果 i=n 到 0
             double speed = (b[i-1] >= (i < n ? a[i] : 0.0) ? 1.3 : 0.7);
             if (i < n) // 只有当目标是实际的 a[i] 时才考虑传送+爬
                dp[i][1] = min(dp[i][1], dp[i-1][1] + climb_teleport_cost / speed);
        }
         // 代码简化版（假设 a[n] 可以访问但不影响最终 dp[n][0] 的计算）:
         if (i < n) { // 仅当 i < n 时，传送点 a[i] 才有意义
            dp[i][1] = dp[i][0] + (double)a[i] / 0.7;
            dp[i][1] = min(dp[i][1], dp[i-1][1] + abs((double)b[i-1] - a[i]) / (b[i-1] >= a[i] ? 1.3 : 0.7));
         } else { // i == n, dp[n][1] 理论上不需要，设为 inf
            dp[n][1] = inf; 
         }


    }
    // 输出结果，保留两位小数
    cout << fixed << setprecision(2);
    cout << dp[n][0] << "\n";

    return 0; // 程序正常结束
}