经典dp题
由题目可知,青蛙到达一根竹竿只有两种情况:
(1) 从上根竹竿瞬移过来
(2) 从上根竹竿沿着x轴爬过来
由此可以定义2维状态f[i][j],j只有0、1两种对应上面的情况
由此得出状态定义: 从原点出发,第一次到达第j根竹竿的底部或竹竿上的所有情况的集合
属性: 最短的时间
在状态计算之前,先明确几个东西:
a[i]: 当前竹竿的传送门位置
b[i]: 上一根竹竿传送到当前竹竿的位置
所以f[i - 1][1]一定在b[i - 1]的位置
上根竹竿的上面这个位置指的是由上上根竹竿传送过来
f[i][0]可以由上根竹竿底部然后沿着x轴走过来f[i - 1][0] + x[i] - x[i - 1],
也可以从上根竹竿的上面先走到竹竿底部,然后再沿着x轴走过来f[i - 1][1] + (b[i - 1] - 0) / 1.3 + x[i] - x[i - 1]
f[i][1]可以由上根竹竿的底部先走到上根竹竿的传送门,再瞬移过来f[i - 1][0] + (a[i - 1] - 0) / 0.7
也可以从上根竹竿的上面,走到上根竹竿的传送门,再瞬移过来f[i - 1][1] + abs(a[i - 1] - b[i - 1]) / 0.7(或1.3)
import java.util.*;
public class Main {
static final int N = (int) 1e5 + 10;
static final int INF = (int) 2e9;
static int[] x = new int[N];
static int[] a = new int[N];
static int[] b = new int[N];
static double[][] f = new double[N][2];
private static double get(int a, int b) {
return a > b ? (a - b) / 1.3 : (b - a) / 0.7;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 1; i <= n; i++) x[i] = sc.nextInt();
for (int i = 1; i < n; i++) {
a[i] = sc.nextInt();
b[i + 1] = sc.nextInt();
}
// 初始化
f[1][0] = x[1];
f[1][1] = x[1] + a[1] / 0.7;
for (int i = 2; i <= n; i++) {
int d = x[i] - x[i - 1];
f[i][0] = Math.min(
f[i - 1][0] + d,
f[i - 1][1] + get(b[i - 1], 0) + d
);
f[i][1] = Math.min(
f[i - 1][0] + get(0, a[i - 1]),
f[i - 1][1] + get(b[i - 1], a[i - 1])
);
}
double res = Math.min(f[n][0], f[n][1] + get(b[n], 0));
System.out.printf("%.2f", res);
}
}