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

chenzefan · 2025-05-09 17:02:15 · 题解

提供一篇 C++ 的题解。

题目传送门

涉及知识

• 动态规划基础与转移。

  思路分析

  本人没有尝试暴力做法，用 dfs 暴力，应该可以拿点分。

来看正解，一眼题目用动态规划，因为容易发现，第 i 根柱子的状态可以由第 i-1 根柱子的状态进行转移。

状态定义——定义一个 dp[N][2]，dp[i][0] 表示不用传送门到达 i 号柱子底部的时间，dp[i][1] 表示使用传送门到达 i 号柱子底部的时间。

此部分代码：

double dp[N][2];

状态初始化——因为求最小值 \min，所以初始值要赋极大值，本人赋值了 0x3f，可供参考。还有，因为原点到第1根柱子之间没有传送门，所以 dp[1][0] 和 dp[1][1] 也要初始化为 x_1。

此部分代码：

memset(dp,0x3f,sizeof(dp)); 
dp[0][0]=0;
dp[1][0]=dp[1][1]=x[1];

状态转移——枚举每一个柱子：

• 如果不走传送门：用 dp[i-1][0] 和 dp[i-1][1] 的较小值 \min 加上横坐标之差进行转移。
• 如果要走传送门：则要先减去传送门起点到底部所需时间，再加上使用传送门的时间，因为要更新到 i 号柱子底部的最少时间，所以还要加上传送门终点到底部的时间。

此部分代码：

for(int i=2;i<=n;i++){//按照题目描述计算时间
        //不用传送门（直接转移） 
        dp[i][0]=min(dp[i-1][1]+x[i]-x[i-1],dp[i-1][0]+x[i]-x[i-1]);
        //使用传送门
        double last=0;
        if(a[i-1]<b[i-2]) last=(b[i-2]-a[i-1])/1.3;
        else last=(a[i-1]-b[i-2])/0.7;
        dp[i][1]=min(dp[i-1][0]+a[i-1]/0.7+b[i-1]/1.3,dp[i-1][1]-b[i-2]/1.3+last+b[i-1]/1.3);
    }

最后求时间只需按照题目描述模拟即可。输出即求到达第 n 根柱子的最小方案，也就是 min(dp[n][0],dp[n][1])。

此部分代码：

printf("%.2lf",min(dp[n][0],dp[n][1]));//输出答案 

注意: dp 数组类型为 double。输出要保留两位小数

如果还没听懂请看代码。

代码（完整版）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],x[N];
double dp[N][2];//状态定义 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",x+i);
    for(int i=1;i<n;i++) scanf("%d%d",a+i,b+i);
    //状态初始化
    memset(dp,0x3f,sizeof(dp)); 
    dp[0][0]=0;
    dp[1][0]=dp[1][1]=x[1];
    //状态转移 
    for(int i=2;i<=n;i++){//按照题目描述计算时间
        //不用传送门（直接转移） 
        dp[i][0]=min(dp[i-1][1]+x[i]-x[i-1],dp[i-1][0]+x[i]-x[i-1]);
        //使用传送门
        double last=0;
        if(a[i-1]<b[i-2]) last=(b[i-2]-a[i-1])/1.3;
        else last=(a[i-1]-b[i-2])/0.7;
        dp[i][1]=min(dp[i-1][0]+a[i-1]/0.7+b[i-1]/1.3,dp[i-1][1]-b[i-2]/1.3+last+b[i-1]/1.3);
    }
    printf("%.2lf",min(dp[n][0],dp[n][1]));//输出答案 
    return 0; 
}