[测试题]line

Description

Input

Output

Sample Input

10 4974
3636 3
6679 70
7182 93
10618 98
14768 23
15242 99
16077 35
23368 46
27723 15
32404 81

Sample Output

0.465308

Hint

题解

典型的 $01$ 分数规划。

我们假设 $x[]$ 中和 $a[]$ 中只保存了选取的点。

依题，要求 $$ans={{sum_i {sqrt{|x[i]-x[i-1]-l|}}} over {sum_i a[i]}}$$

按照 $01$ 分数规划的套路，我们假设有对于当前值更优的解。

$$egin{aligned}ans&geq{{sum_i {sqrt{|x[i]-x[i-1]-l|}}} over {sum_i a[i]}}\ans imes{sum_i a[i]}&geq{sum_i {sqrt{|x[i]-x[i-1]-l|}}}\{sum_i ({ans imes a[i]})}&geq{sum_i {sqrt{|x[i]-x[i-1]-l|}}}\0&geq{sum_i {sqrt{|x[i]-x[i-1]-l|}}}-{sum_i ({ans imes a[i]})}\0&geq{sum_i ({sqrt{|x[i]-x[i-1]-l|}-ans imes a[i]})}end{aligned}$$

那么我们去二分这个 $ans$，每次做一次 $ ext{DP}$ 判断有无更优解即可。

 1 //It is made by Awson on 2017.9.19
 2 #include <map>
 3 #include <set>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <cstdio>
 9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Max(a, b) ((a) > (b) ? (a) : (b))
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 #define Abs(a) ((a) < 0 ? (-(a)) : (a))
19 #define lowbit(x) ((x)&(-(x)))
20 using namespace std;
21 const int INF = ~0u>>1;
22 const int N = 1000; 
23 const double eps = 1e-7;
24 
25 int n, l;
26 int x[N+5], a[N+5];
27 
28 bool judge(double r) {
29     double f[N+5];
30     f[0] = 0;
31     for (int i = 1; i <= n; i++) {
32         f[i] = INF;
33         for (int j = 0; j < i; j++)
34             f[i] = min(f[i], f[j]+sqrt(Abs(x[i]-x[j]-l))-r*a[i]);
35     }
36     return f[n] < eps;
37 }
38 void work() {
39     for (int i = 1; i <= n; i++)
40         scanf("%d%d", &x[i], &a[i]);
41     double L = 0, R = 1e9;
42     while (R - L > eps) {
43         double mid = (L+R)/2.;
44         if (judge(mid)) R = mid;
45         else L = mid;
46     }
47     printf("%.6lf
", L);
48 }
49 
50 int main() {
51     freopen("line.in", "r", stdin);
52     freopen("line.out", "w", stdout);
53     while (~scanf("%d%d", &n, &l))
54         work();
55     return 0;
56 }