当前位置：首页 > article >正文

【蓝桥杯每日一题】蜗牛——动态规划

article 2024/12/24 9:08:44

蜗牛

蓝桥杯每日一题 2024-12-23 蜗牛动态规划

题目描述

今天，一只蜗牛来到了二维坐标系的原点。

在 x 轴上有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0，横坐标分别为 $x_1, x_2, \dots, x_n$ 。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的顶部，也就是坐标 $x_n, 0)$ 。
它只能沿 x 轴上或者竹竿上爬行，在 x 轴上爬行速度为 $\, \text{单位/秒}$ 。由于受到引力影响，蜗牛在竹竿上向上的爬行速度为 $\, \text{单位/秒}$ ，而向下的爬行速度为 $\, \text{单位/秒}$ 。

为了快速到达目的地，它施展了魔法，在第 $i$ 和 $i + 1$ 根竹竿之间建立了传送门 $(0 < i < n)$ 。如果蜗牛位于第 $i$ 根竹竿的高度为 $a_i$ 的位置 $x_i, a_i)$ ，就可以瞬间到达第 $i + 1$ 根竹竿的高度为 $b_{i+1}$ 的位置 $x_{i+1}, b_{i+1})$ 。请计算蜗牛最少需要多少秒才能到达目的地。

解题思路

基本实现思路已在图中表明。

Accepted

#include <iostream>
#include <iomanip>

using namespace std;

const int N = 100010,INF = 0x3f3f3f3f;
int t[N],n,a[N],b[N];
double f[N][2];

double get(int x,int y) {
    // x 是起点  y 是终点
    if(x > y) return (x-y)/1.3;
    else return (y-x)/0.7;
}
 
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++) {
        cin>>t[i];
    }
    for(int i = 1;i < n;i++) {
        cin>>a[i]>>b[i+1];
    }
    for(int i = 1;i <= n;i++) {
        f[i][0] = f[i][1] = INF;
    }

    f[1][0] = t[1];
    for(int i = 2;i <= n;i++) {
        int interval = t[i] - t[i-1]; // 间隔
        // 走到竹竿底部
        f[i][0] = min(f[i-1][0] + interval,f[i-1][1] + interval + get(b[i-1],0));

        // 走到竹竿的b[i]处
        f[i][1] = min(f[i-1][0] + get(0,a[i-1]),f[i-1][1] + get(b[i-1],a[i-1]));
    }
    cout<<fixed<<setprecision(2)<<min(f[n][0],f[n][1]+b[n]/1.3);
    return 0;
}