题目描述
这天,一只蜗牛来到了二维坐标系的原点。
在 x轴上长有 n根竹竿。
它们平行于 y轴,底部纵坐标为 0,横坐标分别为 x1,x2,…,xn。
竹竿的高度均为无限高,宽度可忽略。
蜗牛想要从原点走到第n个竹竿的底部也就是坐标 (xn,0)。
它只能在 x轴上或者竹竿上爬行,在x轴上爬行速度为1单位每秒;由于受到引力影响,蜗牛在竹竿上向上和向下爬行的速度分别为 0.7单位每秒和1.3单位每秒。
为了快速到达目的地,它施展了魔法,在第i和i+1根竹竿之间建立了传送门(0<i<n),如果蜗牛位于第 i根竹竿的高度为 ai的位置(xi,ai),就可以瞬间到达第 i+1根竹竿的高度为 bi+1的位置 (xi+1,bi+1),当然也可以选择不瞬移到第 i+1根竹竿。
请计算蜗牛最少需要多少秒才能到达目的地。
输入格式
输入共 1+n行,第一行为一个正整数 n;
第二行为 n个正整数 x1,x2,…,xn;
后面 n−1行,每行两个正整数 ai,bi+1。
输出格式
输出共一行,一个浮点数表示答案(四舍五入保留两位小数)。
样例
输入样例:
3
1 10 11
1 1
2 1
输出样例:
4.20
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 2e9;
/*
>>闫氏DP分析法:
·开个f[N][2]来表示集合;
·状态表示:
集合——对于当前第i个杆子,f[i][0]表示第一次爬到i杆底部的所有方案,f[i][1]表示第一次爬到i杆身上的
所有方案;
属性——所有方案中花费时间最少的;
·状态计算:
·首先根据样例的输入,可以发现这n个杆子除了第1个和第n个杆子只最多有一个传送站,2~n-1这些杆子则最多
可以有两个传送点,即一个出站口和一个入站口;
·而a[]和b[]两个数组的含义就是,对于第i个杆子来说,a[i]表示第i个杆子的可去往下一个杆子的入站点,
b[i]表示第i个杆子有前一个杆子传送过来的出站点;
·第i杆可以分为f[i][0]和f[i][1]两个子集,这两个子集的计算如下:
->f[i][0]:首先它只能由i-1杆子的底部沿x轴爬过来,所以划分点在于i-1个杆子上;
一种方法是先从i-2个杆子底部爬到i-1个杆子底部,再爬到i个杆子底部;
另一方法是先从i-2个杆子通过传送,到达i-1个杆子身上(也就是到达i-1的出站口b[i-1]),然后
从b[i-1]顺着往下爬到i-1个杆子底部,再然后爬到i个杆子底部;
->f[i][1]:首先它只能由i-1杆子某传送点传送过来,所以划分点还在于i-1杆子上;
一种方法是先从i-1杆子底部爬到i-1杆子上的入口站a[i-1],然后传送到i杆子身上;
另一方法是先从i-1杆子身上,也就是i-1杆子的出口站b[i-1],然后要爬到i-1杆子的入口站a[i-1],
再然后传送到i杆子身上;
>>总结一下:
·->f[i][0]表示的是第一次到达i杆子底部的方案中花费时间最少的,而到达i杆子只能从i-1杆子底部爬过来,但到达
i-1杆子底部又有两种方法:一是先从i-2杆子底部爬过来;二是先从i-2杆子某传送站传送到i-1杆子的出站口,
然后向下爬到i-1杆子底部;
·->f[i][1]表示的是第一次到达i杆子出口站的方案中花费时间最少的,而到达i杆子出口站只能从i-1杆子入口站传送,
但到达i-1杆子入口站又有两种方法:一是先从i-2杆子到达i-1杆子底部,然后从i-1杆子底部向上爬到入口站a[i-1];
二是先从i-2杆子某传送站传送到i-1杆子的出口站b[i-1],然后爬到入口站a[i-1];
*/
int n;
int x[N], a[N], b[N];
double f[N][2];
double get(int d1, int d2) {
if (d1 >= d2) return (d1 - d2) / 1.3;
return (d2 - d1) / 0.7;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i];
for (int i = 1; i <= n - 1; i++) cin >> a[i] >> b[i + 1];
for (int i = 1; i <= n; i++) f[i][0] = f[i][1] = INF;
f[1][0] = x[1];
for (int i = 2; i <= n; i++) {
int dist = x[i] - x[i - 1];
f[i][0] = min(f[i - 1][0] + dist, f[i - 1][1] + dist + get(b[i - 1], 0));
f[i][1] = min(
f[i - 1][1] + get(b[i - 1], a[i - 1]),
f[i - 1][0] + get(0, a[i - 1])
);
}
printf("%.2lf", min(f[n][0], f[n][1] + b[n] / 1.3));
return 0;
}