题目描述
集合:从原点开始走,第一次走到第i根竹竿时,纵坐标的位置在0或b[i]的所有方案的集合。
DP
import java.util.*;
public class Main {
static final int N = 100010;
static final double INF = 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];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 1; i <= n; i++)
x[i] = scanner.nextInt();
for (int i = 1; i < n; i++) {
a[i] = scanner.nextInt();
b[i + 1] = scanner.nextInt();
}
//f[1][1] = INF;//这个集合应该为空 所以给它设为无穷大
//第二种初始化方法 本质是一样的
for (int i = 0; i <= n; i ++ )
f[i][0] = f[i][1] = INF;
f[1][0] = x[1];
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])
);
}
System.out.printf("%.2f\n", Math.min(f[n][0], f[n][1] + b[n] / 1.3));
scanner.close();
}
static double get(int x1, int x2) {
if (x1 < x2) return (x2 - x1) / 0.7;
return (x1 - x2) / 1.3;
}
}