蓝桥杯---蜗牛

蓝桥杯2023年第十四届省赛真题-蜗牛 - C语言网 (dotcpp.com)

动态规划的思想

1. 问题分析：问题的本质是求解蜗牛从起点到终点的最短时间。蜗牛可以选择直接爬行到下一个竹竿的底部，也可以利用传送门来快速移动。

2. 状态定义：在动态规划中，我们需要定义状态以及状态之间的转移。在这里，我们定义两个状态：

   • time_bottom[i]：表示到达第i根竹竿底部的最短时间。
   • time_portal[i]：表示到达第i根竹竿传送门入口的最短时间。

3. 状态转移方程：根据问题的特点，我们可以得到状态之间的转移关系：

   • 对于 time_bottom[i]：

     • 如果当前是最后一根竹竿，则只需考虑从上一根竹竿底部到当前竹竿底部的时间以及从当前竹竿传送门出口到底部的时间，取两者的最小值即可。
     • 如果不是最后一根竹竿，则需要考虑从上一根竹竿底部直接到当前竹竿底部的时间以及从当前竹竿传送门出口到底部的时间，同样取两者的最小值。

   • 对于 time_portal[i]：

     • 考虑到达传送门入口的两种方式：从底部爬到入口，或者从传送门的出口爬到入口。取这两种方式中的最小时间作为到达传送门入口的最短时间。

4. 边界情况处理：在动态规划中，通常需要考虑边界情况。在这个问题中，就是第一个竹竿的情况，需要单独处理。

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建一个Scanner对象以读取输入
        int n = sc.nextInt(); // 读取输入的竹竿数量
        int tree[] = new int[n]; // 记录每根竹竿到原点的距离
        int portal_exit[] = new int[n]; // 记录传送门出口的高度
        int portal_entrance[] = new int[n]; // 记录传送门入口的高度
        double time_bottom[] = new double[n]; // 记录到达每根竹竿底部的最短时间
        double time_portal[] = new double[n]; // 记录到达每根竹竿传送门入口的最短时间

        // 读取每根竹竿到原点的距离
        for (int i = 0; i < n; i++) {
            tree[i] = sc.nextInt();
        }

        // 读取传送门出口和入口的高度
        for (int i = 0; i < n - 1; i++) {
            portal_entrance[i] = sc.nextInt();
            portal_exit[i + 1] = sc.nextInt();
        }

        // 计算第一根竹竿的底部和传送门出口的最短时间
        time_bottom[0] = tree[0]; // 到达第一根竹竿底部的时间
        time_portal[0] = tree[0] + portal_entrance[0] / 0.7; // 到达第一根竹竿传送门入口的时间

        // 计算每根竹竿的最短时间
        for (int i = 1; i < n; i++) {
            if (i == n - 1) { // 如果是最后一根竹竿
                // 从上一根竹竿底部直接到达当前竹竿底部
                double bottom1 = time_bottom[i - 1] + tree[i] - tree[i - 1];
                // 从当前竹竿传送门出口向下爬到底部
                double bottom2 = time_portal[i - 1] + portal_exit[i] / 1.3;
                // 取最小时间作为到达当前竹竿底部的最短时间
                time_bottom[i] = Math.min(bottom1, bottom2);
                break; // 跳出循环
            } else {
                // 计算从上一根竹竿底部直接到达当前竹竿底部的时间
                double bottom1 = time_bottom[i - 1] + tree[i] - tree[i - 1];
                // 计算从当前竹竿传送门出口向下爬到底部的时间
                double bottom2 = time_portal[i - 1] + portal_exit[i] / 1.3;
                // 取最小时间作为到达当前竹竿底部的最短时间
                time_bottom[i] = Math.min(bottom1, bottom2);

                // 计算到达当前竹竿传送门入口的最短时间
                double time_entrance1 = time_bottom[i] + portal_entrance[i] / 0.7; // 从底部爬到入口
                double time_entrance2 = 0;
                if (portal_entrance[i] >= portal_exit[i]) { // 如果入口在出口上面
                    time_entrance2 = time_portal[i - 1] + (portal_entrance[i] - portal_exit[i]) / 0.7; // 向上爬
                } else {
                    time_entrance2 = time_portal[i - 1] + (portal_exit[i] - portal_entrance[i]) / 1.3; // 向下爬
                }
                // 取两种方式中的最小时间作为到达当前竹竿传送门入口的最短时间
                time_portal[i] = Math.min(time_entrance1, time_entrance2);
            }
        }
        System.out.printf("%.2f", time_bottom[n - 1]); // 输出到达最后一根竹竿底部的最短时间
    }