跳转至

题解：P12327 [蓝桥杯 2023 省 Java B] 蜗牛

思路与算法

题目分析

题目描述了一只蜗牛从二维坐标系的原点 \((0, 0)\) 出发，沿着 \(x\) 轴或竹竿爬行，最终到达第 \(n\) 根竹竿的底部 \((x_n, 0)\)。

蜗牛在 \(x\) 轴上的爬行速度为 \(1\) 个单位每秒，在竹竿上向上和向下爬行的速度分别为 \(0.7\) 个单位每秒和 \(1.3\) 个单位每秒。

此外，蜗牛可以利用传送门在相邻竹竿之间快速移动。我们的任务是计算蜗牛到达目的地的最短时间。

解题思路

这道题目，我们可以通过动态规划来解决。

我们令这里有两组数 \(dpg\)，\(dpp\)。其中：

  • \(dpg_i\) 表示到达第 \(i\) 根竹竿底部的最短时间；
  • \(dpp_i\) 表示到达第 \(i\) 根竹竿传送门起点 \((x_i, a_i)\) 的最短时间。

每次移动考虑两种选择：直接爬行或使用传送门。

我们发现，蜗牛到达第 \(i\) 根竹竿底部有以下两种情况：

  • 直接从第 \(i-1\) 根竹竿底部沿 \(x\) 轴爬过来；
  • 通过第 \(i-1\) 根竹竿的传送门传送到第 \(i\) 根竹竿的某个高度，再爬下来。

它们对应的式子就是：

  • \(dpg_{i-1} + (x_i - x_{i-1})\)；
  • \(dpp_{i-1} + b_i \div 1.3\)。

同时，蜗牛到达第 \(i\) 根竹竿传送门起点 \((x_i, a_i)\) 的最短时间也可以由两种方式得到：

  • 从第 \(i\) 根竹竿底部爬上来，
  • 从第 \(i-1\) 根竹竿的传送门终点 \(x_i, b_{i-1}\) 爬过来。

它们对应的式子就是：

  • \(dpg_i + a_i \div 0.7\)；
  • 当 \(b_{i-1} \ge a_i\) 时：
  • \(dpp_{i-1} + (b_{i-1} - a_i) \div 1.3\)；
  • 当 \(b_{i-1} < a_i\) 时：
  • \(dpp_{i-1} + (a_i - b_{i-1}) \div 0.7\)。

具体细节如下：

  1. 从地面到下一根竹竿的地面：

    • 直接沿 \(x\) 轴爬行。

  2. 使用传送门：

    • 从第 \(i\) 根竹竿的传送门起点 \((x_i, a_i)\) 传送到第 \(i+1\) 根竹竿的 \((x_{i+1}, b_{i+1})\)。

  3. 从地面爬到传送门起点：

    • 从第 \(i\) 根竹竿的地面爬到传送门起点 \((x_i, a_i)\)。
    • 如果从第 \(i-1\) 根竹竿的传送门终点 \((x_i, b_i)\) 爬到 \((x_i, a_i)\)，时间取决于 \(b_i\) 和 \(a_i\) 的相对高度。

代码

这里我稍微做了一些初始化：

我将 \(dpg_1\) 初始化为 \(x_1\)，表示从原点直接到达第一根竹竿底部的时间。

剩下的就好说啦！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n;
int x[N];
double dpg[N];
double dpp[N];
int prev_b;     // 记录前一个传送门的b值
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &x[i]);

    // 初始化
    if (n >= 1) {
        dpg[1] = x[1];
    }
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);

        // 计算到达当前传送门起点的最短时间
        double mint;
        if (i == 1) {
            // 第一次只能从地面爬上来
            mint = dpg[i] + a / 0.7;
        } else {
            // 两种选择：从地面爬上来 或 从前一个传送门过来
            double op1 = dpg[i] + a / 0.7;
            double op2 = dpp[i-1] + (prev_b >= a ? (prev_b-a)/1.3 : (a-prev_b)/0.7);
            mint = min(op1, op2);
        }
        dpp[i] = mint;
        prev_b = b;  // 保存当前b值供下次使用
        // 计算到达下一根竹竿底部的最短时间
        dpg[i+1] = min(dpg[i] + (x[i+1]-x[i]), dpp[i] + b/1.3);
    }
    // round()函数用于取四舍五入的整数值，这里保留两位小数，所以要先乘100
    printf("%.2lf", round(dpg[n] * 100) / 100.0);
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using System;

class Program
{
    const int N = 100005;
    static int n;
    static int[] x = new int[N];
    static double[] dpg = new double[N];
    static double[] dpp = new double[N];
    static int prev_b; // 记录前一个传送门的b值

    static void Main()
    {
        n = int.Parse(Console.ReadLine());
        string[] xInput = Console.ReadLine().Split();
        for (int i = 1; i <= n; i++)
            x[i] = int.Parse(xInput[i - 1]);

        // 初始化
        if (n >= 1)
        {
            dpg[1] = x[1];
        }
        for (int i = 1; i < n; i++)
        {
            string[] abInput = Console.ReadLine().Split();
            int a = int.Parse(abInput[0]);
            int b = int.Parse(abInput[1]);

            // 计算到达当前传送门起点的最短时间
            double mint;
            if (i == 1)
            {
                // 第一次只能从地面爬上来
                mint = dpg[i] + a / 0.7;
            }
            else
            {
                // 两种选择：从地面爬上来 或 从前一个传送门过来
                double op1 = dpg[i] + a / 0.7;
                double op2 = dpp[i - 1] + (prev_b >= a ? (prev_b - a) / 1.3 : (a - prev_b) / 0.7);
                mint = Math.Min(op1, op2);
            }
            dpp[i] = mint;
            prev_b = b; // 保存当前b值供下次使用

            // 计算到达下一根竹竿底部的最短时间
            dpg[i + 1] = Math.Min(dpg[i] + (x[i + 1] - x[i]), dpp[i] + b / 1.3);
        }
        // Math.Round()函数用于取四舍五入的值，这里保留两位小数
        Console.WriteLine($"{Math.Round(dpg[n], 2):F2}");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Scanner;

public class Main {
    static final int N = 100005;
    static int n;
    static int[] x = new int[N];
    static double[] dpg = new double[N];
    static double[] dpp = new double[N];
    static int prev_b; // 记录前一个传送门的b值

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            x[i] = scanner.nextInt();
        }

        // 初始化
        if (n >= 1) {
            dpg[1] = x[1];
        }
        for (int i = 1; i < n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            // 计算到达当前传送门起点的最短时间
            double mint;
            if (i == 1) {
                // 第一次只能从地面爬上来
                mint = dpg[i] + a / 0.7;
            } else {
                // 两种选择：从地面爬上来 或 从前一个传送门过来
                double op1 = dpg[i] + a / 0.7;
                double op2 = dpp[i - 1] + (prev_b >= a ? (prev_b - a) / 1.3 : (a - prev_b) / 0.7);
                mint = Math.min(op1, op2);
            }
            dpp[i] = mint;
            prev_b = b; // 保存当前b值供下次使用
            // 计算到达下一根竹竿底部的最短时间
            dpg[i + 1] = Math.min(dpg[i] + (x[i + 1] - x[i]), dpp[i] + b / 1.3);
        }
        // Math.round()函数用于取四舍五入的整数值，这里保留两位小数，所以要先乘100
        System.out.printf("%.2f", Math.round(dpg[n] * 100) / 100.0);
        scanner.close();
    }
}