【题解】CF489E Hiking

题目描述

一个旅行者正在计划沿着河水进行一场水上远足。经过探测，他已经探明了这条河上适合晚上休息的n个地点，记录了这些地点与出发点的距离。

上述的每一个地点都有一个美丽度。也就是说，对于第i个地点，它和起点的距离为$x_i$，它的美丽度为$b_i$​。

上述的每一个地点都在出发点的下游，且这个旅行者在旅行的时候只会顺流而下。

简言之，我们可以把河流看成一个数轴，出发点的坐标是0，第i个地点的坐标是$x_i$​。旅行者只会沿正方向前进。

这个旅行者对他一天的前进距离，设定了一个基准值l，如果他某天的所前进的距离大于或小于了这个基准值，都会使他疲劳。假设他一天走了$r_i$的距离，那么他产生的疲劳值为$\sqrt{|r_i-l|}$

​，他整个旅程的总疲劳值为每一天的疲劳值之和。

显然，这个旅行者晚上需要休息，所以必须到达一个休息地点才能结束一天的行程，并在这个地点过夜。类似于上面的定义，假设他当天晚上在第i个地点休息，那么他当天的舒适度为这个地点的美丽度，即$b_i$​。他整个旅程的总舒适度是每一天（包括最后一天）的舒适度之和。

现在他希望你帮助他规划旅游路线，确定出每一天在哪个地点休息，他对旅游的天数没有要求，但是要求最后一天必须在第n个地点休息。他希望你的这个规划足够合理，使得这次旅行的总疲劳值除以总舒适度的结果最小化。

输入格式

第一行，两个整数，n，l，分别表示休息地点的个数和每日旅行距离的基准值。

接下来n行，每行两个整数，$x_i$，$b_i$，保证$x_i$严格递增。

输出格式

按顺序输出你所规划的每一天的休息地点的序号，用空格隔开，必须以n号地点结束。

题解

其实挺水的。 要让上下和比值最小，显然0/1分数规划。 设L为每次走的疲劳度，有 $$p=\frac{{\sum }_{}^{}L}{{\sum }_{}^{}{b}_i}$$

则 $$\sum (L-p\times b_i)=0$$ 然后二分p，求1到n的最短路，其中(u,v)之间有一条边权为$\sqrt{|(x_v-x_u)-l|}-p\times b_v$​ 的单向边，构成一个DAG求最短路。设$d{p}_i$为到i的最短距离递推可得，若值非负则增大p。 至于路径就在递推时记录一下前驱即可。

#include<bits/stdc++.h> using namespace std; const int M=1e6+5; int n,L; int pre[M]; double dp[M]; struct node{ int x,y; }; node a[M]; bool check(double mid){ for(int i=1;i<=n;i++) dp[i]=1e19; dp[0]=0; for(int i=0;i<=n;i++){ for(int j=i+1;j<=n;j++){ double tot=sqrt(abs(a[j].x-a[i].x-L))+dp[i]-a[j].y*mid; if(dp[j]>=tot){ dp[j]=tot; pre[j]=i; } } } if(dp[n]>=0) return 1; else return 0; } void find(int z){ if(!z) return; find(pre[z]); printf("%d ",z); return; } int main(){ scanf("%d %d",&n,&L); for(int i=1;i<=n;i++){ scanf("%d %d",&a[i].x,&a[i].y); } double l=0,r=1e8,mid; while(abs(r-l)>1e-9){ mid=(l+r)/2.0; if(!check(mid)) r=mid; else l=mid; } find(n); return 0; }