dp|Codeforces Round #277.5(Div. 2)E. Hiking【Dp+01分数规划】 01分数规划|二分查找

E. Hiking time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output A traveler is planning a water hike along the river. He noted the suitable rest points for the night and wrote out their distances from the starting point. Each of these locations is further characterized by itspicturesqueness, so for the i-th rest point the distance from the start equals xi, and its picturesqueness equalsbi. The traveler will move down the river in one direction, we can assume that he will start from point0 on the coordinate axis and rest points are points with coordinatesxi.
Every day the traveler wants to cover the distance l. In practice, it turns out that this is not always possible, because he needs to end each day at one of the resting points. In addition, the traveler is choosing between two desires: cover distance l every day and visit the most picturesque places.
Let's assume that if the traveler covers distance rj in a day, then he feels frustration
文章图片
, and his total frustration over the hike is calculated as the total frustration on all days.
Help him plan the route so as to minimize therelative total frustration: the total frustration divided by the total picturesqueness of all the rest points he used.
The traveler's path must end in the farthest rest point.
Input The first line of the input contains integers n,?l (1?≤?n?≤?1000,?1?≤?l?≤?105) — the number of rest points and the optimal length of one day path.
Then n lines follow, each line describes one rest point as a pair of integersxi,?bi (1?≤?xi,?bi?≤?106). No two rest points have the same xi, the lines are given in the order of strictly increasingxi.
Output Print the traveler's path as a sequence of the numbers of the resting points he used in the order he used them. Number the points from 1 ton in the order of increasing xi. The last printed number must be equal ton.
Examples Input

5 9 10 10 20 10 30 1 31 5 40 10

Output

1 2 4 5

Note In the sample test the minimum value of relative total frustration approximately equals 0.097549. This value can be calculated as

dp|Codeforces Round #277.5(Div. 2)E. Hiking【Dp+01分数规划】

文章图片
.

题目大意：
给你N个元素，每个元素两个属性，每按序选择一个元素之后，分子获得

文章图片
价值，分母获得bi价值
【dp|Codeforces Round #277.5(Div. 2)E. Hiking【Dp+01分数规划】】问最终分子和/分母和最小的选取方案。（第N个必须选）；

思路：

1、很显然问题属于01分数规划问题。
当有求：Σ（a【i】）/Σ（b【i】）的最小（大）值的时候，我们可以将问题转化变成减法：
设定函数F（L）=Σ（a【i】）-L*Σ（b【i】）；
若此时F（L）<0，那么肯定有Σ（a【i】）-L*Σ（b【i】）<0，那么就有：Σ（a【i】）/Σ（b【i】）根据化出的等式可以得知，我们有比L更小的结果。那么我们这里可以二分枚举这个L，同时也就是在二分枚举最终的答案。
若有F（L）<0，我们可以继续减小答案，反之我们要增大答案。

2、在判定F（L）的时候，我们希望最终结果尽可能的小，那么这里引用dp，设定dp【i】表示到第i个物品，选取出来的最小值。
那么就有：dp【i】=min（dp【i】，dp【j】+选择第i个物品时候获得的价值）；
那么如果dp【n】<0，那么F（L）就小于0.
累次二分即可。
因为二分的l，r都是double类型，我们不妨不要控制精度，去for二分过程次数即可。

Ac代码：

#include #include #include #include using namespace std; struct node { int x,y; }a[15000]; int n,l; int output[15000]; int ans[15000]; int pre[15000]; double dp[15000]; int Slove(double L) { dp[0]=0; for(int i=1; i<=n; i++)dp[i]=1000000000000; for(int i=1; i<=n; i++) { for(int j=0; j0) { output[cnt++]=now; now=ans[now]; } for(int i=cnt-1; i>=0; i--) { printf("%d ",output[i]); } printf("\n"); } }