CodeForces 489E Hiking

题意：

数轴上有n（1000）个点 每个点有个距离源点的距离xi和美观值bi 主人公站在源点 他希望每步步长len 但每一步必须落在n个点其中一个上 且行进方向唯一 走到点n后可以计算旅行的价值

对于所有走过的点i val = sum( sqrt( abs(x[i]-x[i-1]-len) ) / b[i] ) 目标val尽量小 打印路径方案

思路：

第一次做分数规划题 这题是比较典型的01规划

简单描述一下01规划 就是 ans = sum(ci*xi)/sum(di*xi) 其中xi为{0,1}

常规的解法是变形上述式子 F(ans) = sum(ci*xi) - sum(di*xi) * ans 这时我们将ans当成自变量 构造一个函数 容易发现F是单调的 那么就可以二分ans 将求解最值问题转换成判定可行性问题

对于本题 我们可以将val变形 val = sum(sqrt( abs(x[i]-x[i-1]-len) )/sum(b[i])

那么也可以构建F函数 F(val) = sum(sqrt( abs(x[i]-x[i-1]-len) ) - sum(b[i]) * val 这时我们发现这个表达式由于计算中存在i和i-1位置的联系所以不是那么简单 但是也可以发现 我们将原本的除法式子变成了减法式子 这就会出现承袭性！！ 我们可以利用dp计算状态之间的转移 dp[i] = dp[j] + sqrt( abs(x[i]-x[j]-len ) - b[i] * val （真谛就是用dp[j]包含了F中的sum）

这时二分val是logn的 对于每次的val我们可以用n^2的dp进行判定

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include