题意：
数轴上在起点 \(s\) 和终点 \(t\) 间的整点中有 \(n\) 个关键点，第 \(i\) 个关键点位置为 \(c_i\)，可获得 \(m_i\) 的价值。你可以从起点开始，每次跳至多 \(z\) 个点（跨过中间的点），而每到达一个 \(s\) 以外的点需要支付 \(a\) 的代价，求走到终点的最大价值。
\(0\le s\le c_i\le t \le 10^9,n\le 10^5\)
这种题目一眼 DP 好吧
设 \(f_i\) 表示前 \(i\) 个关键点的答案，首先考虑 \(O(n^2)\) 的暴力转移
\[f_i = \min\{f_j + \lceil \frac{c_i-c_j}D \rceil \cdot a_i - m_i \} \\ \]然后有个蠢蛋打表打小了，以为满足决策单调性QwQ
发现优化的瓶颈在于这个烦人的上取整除法
众所周知，上下取整，取模之类的运算都可以拆成普通的运算
发现 \(c_i,c_j\) 同时加 \(k\cdot D\) 并不会影响上取整（即其相对大小关系）带来的贡献，那么我们不妨将这个取整拆开？
\(c_i = k_i \cdot D + b_i\)
成功将贡献转移到 \(b_i,b_j\) 的大小关系上！
\[f_i=\min\{ f_j+(k_i-k_j + \lceil \frac{b_i-b_j}D \rceil) \cdot a_i \} - m_i \\ \because b_i,b_j \in [0,D) \therefore b_i-b_j \in (-D,D) \]这样我们就让烦人的上取整简化成 \([b_i>b_j]\) ，于是丢到以 \(b_i\) 为下标的 最小值权值线段树 里去做就行了
标签：le,NOIP,--,线段,T2,cdot,取整,DP,关键点 From： https://www.cnblogs.com/sukiqwq/p/18528562总结：拆 DP 中难求的贡献？权值线段树！