在坐标轴上有 n ( 1 ≤ n ≤ 1000 ) n(1≤n≤1000) n(1≤n≤1000)个景点，第i个景点坐标为 x i ( 1 ≤ x i ≤ 1 0 6 ) x_i(1≤x_i≤10^6) xi(1≤xi≤106)，美丽度为 b i ( 1 ≤ b i ≤ 1 0 6 ) b_i(1≤b_i≤10^6) bi(1≤bi≤106)。数据保证xi严格递增。一个人从坐标0出发，每天行进一段大于0的距离到达坐标更大的景点，他希望每天正好行进 L ( 1 ≤ L ≤ 1 0 5 ) L(1≤L≤10^5) L(1≤L≤105)距离，但他只能在景点停下。如果他某天的行进距离为r，那么当天的不满足度为 ∣ L − r ∣ \sqrt{|L-r|} ∣L−r∣ ，同时他会获得当天旅程结束所停在的景点的美丽度。最终他要停在n号节点。求使得 ∑ ∣ L − r ∣ ∑ b \frac{\sum\sqrt{|L-r|}}{\sum b} ∑b∑∣L−r∣ 取最小值的任意方案，其中 ∣ L − r ∣ {\sqrt{|L-r|}} ∣L−r∣ 表示每天的不满足度之和， ∑ b \sum b ∑b表示每天停留的景点的美丽度之和。 传送门
这道题目是01分数规划的板题。 首先考虑二分，我们二分一个 m i d mid mid，使 ∑ ∣ L − r ∣ ∑ b ≤ m i d \frac{\sum\sqrt{|L-r|}}{\sum b}\leq mid ∑b∑∣L−r∣ ≤mid → ∑ ∣ L − r ∣ − m i d ∗ ∑ b ≤ 0 \rightarrow \sum\sqrt{|L-r|}-mid*\sum b\leq 0 →∑∣L−r∣ −mid∗∑b≤0 → ∑ ∣ L − ( x [ i ] − x [ j ] ) ∣ − m i d ∗ ∑ b ≤ 0 \rightarrow \sum\sqrt{|L-(x[i]-x[j])|}-mid*\sum b\leq 0 →∑∣L−(x[i]−x[j])∣ −mid∗∑b≤0 于是我们写出一个方程式： f [ i ] = f [ j ] + ∣ L − ( x [ i ] − x [ j ] ) ∣ − m i d ∗ b [ i ] f[i]=f[j]+\sqrt{|L-(x[i]-x[j])|}-mid*b[i] f[i]=f[j]+∣L−(x[i]−x[j])∣ −mid∗b[i] 当 f [ n ] ≤ 0 f[n]\leq 0 f[n]≤0时 m i d mid mid符合条件。 对于输出方案，我们用存前驱的方法，递归输出答案就行了。 初始值 f [ 0 ] = 0 f[0]=0 f[0]=0，其他为最小值。
