【蓝桥杯每日一题】蜗牛—

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

embedded/2024/12/26 1:35:53/

蜗牛

蓝桥杯每日一题 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;
}