网站源码查看_贵阳做网站找哪家好_百度网站推广怎么做_seo零基础培训

蜗牛

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

题目描述

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

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

思考

这道题可以算是较为简单的动态规划，动态转移都是比较直接的，那么首先要观察的是答案该怎么求，然后从答案上递推之前的该怎么求；这道题最主要的是维护两个状态，分别计算，最后再求答案！

备赛交流

蓝桥杯备赛交流：可以+v：xiaoyu208H （备注：蓝桥杯）
想要一起讨论的可以添加！！！