【題解】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;
}