一道好题
首先肯定是DP，考虑如何DP
我们发现可以尝试按照乘坐的列车编号的序列进行DP
设\(f[i]\)表示某种列车序列，最后一趟车是第\(i\)个班次的最小花费
那么显然有\(f[i]=f[j]+A(p_i-q_k)^2+B(p_i-q_j)+C\)
打开之后发现有\(i\)和\(j\)的乘积项，所以想到斜率优化
移项后变成\(2Ap_iq_j+f_i-Ap_i^2-Bp_i-C=f_j+Aq_j^2-Bq_j\)，其中要求\(y_j=x_i,q_j≤p_i\)
考虑如何优化，我们肯定要将原来的列车班次进行某种排序，然后进行线性DP
这里肯定要么按照\(p\)排序，要么按照\(q\)排序
我们先按照\(q\)排序，不难发现是维护斜率单调递增
我们把每一个已经DP好了的\(f[i]\)按照其\(y\)值放在对应的单调队列里面（也就是一共有\(n\)个单调队列），在计算某一个\(f[i]\)的时候，我们只需要在\(x_i\)对应的单调队列里面去查找即可
这样就对了吗？
其实是不行的。首先，\(2Ap_i\)显然不一定单调，所以我们要用二分，而且还要先用二分在这个单调队列里面查找出来满足\(q_j≤p_i\)的位置；其次，可能存在一种情况，如下
如图所示，\(4\)号点的进行会将\(3\)号点弹出去，但有可能\(3\)号点是满足\(q_j≤p_i\)的最大位置，那么\(3\)号点是有可能成为最优决策的
那么解决这个的办法是什么？我们就选择不弹出某个点，而是记录某个点如果进行普通的斜率优化的单调队列的话，他的前一个点是哪一个点，设为\(t[i]\)。假设新进来一个点，我们就比较这个点和当前单调队列的最后一个点的斜率与当前单调队列的最后一个点和其\(t\)（设这个点为\(x\)）的斜率大小来决定是否“弹出”当前单调队列的最后一个点（注意我们并不会真的弹出当前单调队列的最后一个点）；如果要“弹出”，那么就继续比较新进来的这个点和\(x\)的斜率与\(x\)和其\(t\)的斜率来决定是否“弹出”\(x\)，依次类推。不难发现时间复杂度仍然正确（相当于还是每个点最多进队出队一次）。但是这个做法对后面的二分查找就很麻烦了，我只想到了倍增
提醒一下，如果某一趟班次的\(x=1\)，这一趟班次不一定非要放在第一个，我们可以先做其他车，最后回到\(1\)号站，然后再作这一趟班次，可能时间会更优
以上解法是对\(q\)排序，但是代码很难写，那么我们尝试对\(p\)排序
此时对\(p\)排序之后，就解决了斜率不是单调递增的问题（指解决的这个问题：首先，$2Ap_i$显然不一定单调，所以我们要用二分）
然后仍然需要满足\(y_j=x_i,q_j≤p_i\)
第一个条件的处理跟之前一样，就不赘述了
问题是第二个条件的处理
我们想的是某一时刻，当我们更新\(f[i]\)的时候，对应的单调队列的所有点都可以用，就可以忽略第二个条件了
为了达到这种效果，我们更新了\(f[i]\)之后，不要马上把\(f[i]\)插入其对应的单调队列，而是选择放到一个桶里面（对应这一趟班次的\(p\)值）；然后我们在每次更新\(f[i]\)之前，先把所有小于等于\(p_i\)的桶里面的班次全部插入到对应的单调队列里面就好了
标签：班次,队列,回家,路线,斜率,一个点,排序,单调 From： https://www.cnblogs.com/dingxingdi/p/18052535