第十四届蓝桥杯省赛JavaB组 - 蜗牛_蓝桥杯第14届b组

 5400. 蜗牛 - AcWing题库

​​​

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

在 x轴上长有 n 根竹竿。

它们平行于 y轴，底部纵坐标为 00，横坐标分别为 x1,x2,…,xn。

竹竿的高度均为无限高，宽度可忽略。

蜗牛想要从原点走到第 n个竹竿的底部也就是坐标 (xn,0)。

它只能在 x 轴上或者竹竿上爬行，在 x 轴上爬行速度为 11 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 0.70.7 单位每秒和 1.31.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

输出格式

输出共一行，一个浮点数表示答案（四舍五入保留两位小数)。

数据范围

对于 20%20% 的数据，保证 n≤15；
对于 100%100% 的数据，保证 1≤n≤105，1≤ai,bi≤104，1≤x1<x2<…<xn≤109

输入样例：

3
1 10 11
1 1
2 1

输出样例：

4.20

样例解释

蜗牛路线：

(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)，花费时间为 1+10.7+0+11.3+1≈4.20

 

很经典的一道状态机dp题目，我最开始看完题目使用的是dfs，但复杂度太高，一般dfs都能转为dp，但自己dp能力也弱，看完大佬题解后总结一下，

蜗牛经过一个竹杠有两种方式选择，一种是直接从竹杠底部过去，一种是经过当前传送门达到下一竹杠某位置，设置第一种方式状态为0，表示不经过当前传送门，第二种方式状态为1，表示经过当前传送门，定义 f[i][j] 表示达到第 i 根竹杠 j 种状态所用时间， 最终结果就为 f[n][0]，因为题目要求到达 n 根竹杠底部最短时间，

根据题目，可以发现，dp的状态计算，无论 f[i][j],都可以从 f[i-1][0] 和 f[i-1][1] 直接计算出来，然后min 取最小值。

f[i][0] 状态转移方程：

1. 从上一个竹竿的底部转移过来，即：
f[i][0]=f[i−1][0]+x[i]−x[i−1]
2. 从上一个竹竿的传送门转移过来，即：
f[i][0]=f[i−1][1]+b[i−1]/1.3

f[i][1] 状态转移方程：

1. 从上一个竹竿的底部转移过来，即：
f[i][1]=f[i−1][0]+x[i]−x[i−1]+a[i]/0.7

2.从上一个竹杠传送门过来：

因为需要判断上一个竹杠传送门过来后是在当前竹杠传送门上分还是下方，在当前竹杠传送门上分就需要向下移动，否则反之。

f[i][1]=f[i−1][1]+abs(a[i]−b[i−1])/(b[i−1] ≥ a[i]?1.3:0.7)

所以
f[i][0]=min(f[i−1][0]+x[i]−x[i−1],f[i−1][1]+b[i−1]/1.3)
f[i][1]=min(f[i][0]+a[i]/0.7,f[i−1][1]+abs(a[i]−b[i−1])/(b[i−1] ≥ a[i]?1.3:0.7))

另外初始化就很明了，

f[1][0] = x[1], 

f[1][1] = a[1] / 0.7 + x[1];

AC code：

#include <bits/stdc++.h>
using namespace std;
int n;
int x[100010];
int a[100010];
int b[100010];
double f[100010][2];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 1; i < n; i++) cin >> a[i] >> b[i];
	
	f[1][0] = x[1], f[1][1] = a[1] / 0.7 + x[1];
	for (int i = 2; i <= n; i++) {
		f[i][0] = min(f[i - 1][0] + x[i] -x[i-1], f[i - 1][1] + b[i - 1] / 1.3);
		double s = 0;
		if (b[i - 1] >= a[i]) s = (b[i - 1] - a[i]) / 1.3;
		else s = (a[i] - b[i - 1]) / 0.7;
		f[i][1] = min(f[i][0] + a[i] / 0.7, f[i - 1][1] + s);
	}
	printf("%.2lf", f[n][0]);
}