【題解】CF489E Hiking

題目描述

一個旅行者正在計劃沿著河水進行一場水上遠足，經過探測，他已經探明了這條河上適合晚上休息的n個地點，記錄了這些地點與出發點的距離，

上述的每一個地點都有一個美麗度，也就是說，對于第i個地點，它和起點的距離為 x i x_i xi?，它的美麗度為 b i b_i bi??，

上述的每一個地點都在出發點的下游，且這個旅行者在旅行的時候只會順流而下，

簡言之，我們可以把河流看成一個數軸，出發點的坐標是0，第i個地點的坐標是 x i x_i xi??，旅行者只會沿正方向前進，

這個旅行者對他一天的前進距離，設定了一個基準值l，如果他某天的所前進的距離大于或小于了這個基準值，都會使他疲勞，假設他一天走了 r i r_i ri?的距離，那么他產生的疲勞值為 ∣ r i ? l ∣ \sqrt {| r_i-l |} ∣ri??l∣ ?

?，他整個旅程的總疲勞值為每一天的疲勞值之和，

顯然，這個旅行者晚上需要休息，所以必須到達一個休息地點才能結束一天的行程，并在這個地點過夜，類似于上面的定義，假設他當天晚上在第i個地點休息，那么他當天的舒適度為這個地點的美麗度，即 b i b_i bi??，他整個旅程的總舒適度是每一天（包括最后一天）的舒適度之和，

現在他希望你幫助他規劃旅游路線，確定出每一天在哪個地點休息，他對旅游的天數沒有要求，但是要求最后一天必須在第n個地點休息，他希望你的這個規劃足夠合理，使得這次旅行的總疲勞值除以總舒適度的結果最小化，

輸入格式

第一行，兩個整數，n，l，分別表示休息地點的個數和每日旅行距離的基準值，

接下來n行，每行兩個整數， x i x_i xi?， b i b_i bi?，保證 x i x_i xi?嚴格遞增，

輸出格式

按順序輸出你所規劃的每一天的休息地點的序號，用空格隔開，必須以n號地點結束，

題解

其實挺水的，
要讓上下和比值最小，顯然0/1分數規劃，
設L為每次走的疲勞度，有
p = ∑ L ∑ b i p={{\sum^{}_{}{L}} \over {\sum^{}_{}{b_i}}} p=∑?bi?∑?L?

則
∑ ( L ? p × b i ) = 0 {{\sum^{}_{}{(L-{p \times b_i)}}}}=0 ∑?(L?p×bi?)=0
然后二分p，求1到n的最短路，其中(u,v)之間有一條邊權為 ∣ ( x v ? x u ) ? l ∣ ? p × b v \sqrt {| (x_v-x_u)-l |}?{p \times b_v} ∣(xv??xu?)?l∣ ??p×bv?? 的單向邊，構成一個DAG求最短路，設 d p i dp_i dpi?為到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;
}