我们先考虑只有 c=0 怎么做。 一个单纯的想法是 \mathcal{O}(n^2) 的经典 \text{dp}： f_i \leftarrow \max(f_j)+b_i \qquad |a_i-a_j| \leq k(t_i-t_j) 上面的做法加上离散化即可做到 \mathcal{O}(m^2)，但是这还不够。 我们再观察一下转移条件： |a_i-a_j| \leq k(t_i-t_j) \Rightarrow \begin{cases} a_i-a_j \leq k(t_i-t_j) \ a_j-a_i \leq k(t_i-t_j) \end{cases}\ \begin{cases} a_i-kt_i \leq a_j-kt_j \ a_i+kt_i \geq a_j+kt_j \end{cases} 不妨设 A_i=a_i-kt_i,B_i=a_i+kt_i，转移条件变为 \begin{cases} A_i \leq A_j \ B_i \geq B_j \end{cases}。 二维数点问题，树状数组维护即可。 那 c=1 怎么办？我们同时维护最小答案，c=1 时交叉转移就好。