感谢收税穫送来的 trick。

题意

一条数轴，一个人要从位置 $k$ 走到 $m$，一次至多走 $d$ 格，消耗 $a$ 的体力。现还有 $n$ 个关键点，第 $i$ 个关键点位置 $t_i$，走到可以恢复 $b_i$ 体力。求走到 $m$ 能够拥有最大体力。

思路

你会贪吗？我不会。所以我们显然考虑 dp。

我们只关心关键点（不妨把 $k,m$ 也记为分别记为关键点 $0$、$n+1$，恢复体力为 $0$）。于是有如下转移方程：

$$dp_i=b_i+\max\limits_{j=0}^{i-1}\{dp_j-a\times\lceil\dfrac{t_i-t_j}{d}\rceil\}$$

答案为 $dp_{n+1}$。

考虑如何把这个除法上取整搞掉。考虑将 $t_i$ 表示为 $c_i\times d+e_i$ 的形式，我们有：

$$dp_i=b_i+\max\limits_{j=0}^{i-1}\{dp_j-a\times\lceil\dfrac{(c_i-c_j)\times d+(e_i-e_j)}{d}\rceil\}\\ =b_i+\max\limits_{j=0}^{i-1}\{dp_j-a\times(c_i-c_j+[e_i>e_j])\}\\ =(b_i-a\times c_i)+\max\limits_{j=0}^{i-1}\{(dp_j+a\times c_j)-a\times[e_i>e_j]\}\\$$

显然 $[e_i>e_j]$ 的值只有两种。我们按照 $e_i$ 分为 $e_j\in [0,e_i)$ 和 $e_j\in [e_i,d)$ 两类，使用一个值域为 $[0,d)$ 的动态开点线段树，将 $dp_j+a\times c_j$ 的值挂到 $e_j$ 位置上，做单点修改区间最大值即可。

时间复杂度 $O(n\log V)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll t[100002], b[100002], c[100002], e[100002], d, a, n, idx, rt, dp[100002];
struct node { ll s, ls, rs; } tr[2000002];
void update(ll &x, ll l, ll r, ll p, ll v) {
	if (!x) tr[x = ++ idx].s = -inf;
	tr[x].s = max(tr[x].s, v);
	if (l == r) return ;
	ll mid = l + r >> 1;
	if (mid >= p) update(tr[x].ls, l, mid, p, v);
	if (mid <  p) update(tr[x].rs,mid+1,r, p, v);
}
ll query(ll x, ll l, ll r, ll ansl, ll ansr) {
	if (ansl > ansr || !x) return -inf;
	if (ansl <= l && ansr >= r) return tr[x].s;
	ll mid = l + r >> 1, res = -inf;
	if (mid >= ansl) res = max(res, query(tr[x].ls, l, mid, ansl, ansr));
	if (mid <  ansr) res = max(res, query(tr[x].rs,mid+1,r, ansl, ansr));
	return res;
}
int main() {
	cin >> t[0] >> t[1] >> d >> a >> n;
	t[++ n] = t[1];
	for (ll i = 1; i < n; i ++ ) cin >> t[i] >> b[i]; 
	for (ll i = 0; i <= n; i ++ ) c[i] = t[i] / d, e[i] = t[i] % d;
	update(rt, 0, d - 1, e[0], c[0] * a);
	for (ll i = 1; i <= n; i ++ ) {
		dp[i] = b[i] - c[i] * a + max(query(rt, 0, d - 1, 0, e[i] - 1) - a, query(rt, 0, d - 1, e[i], d - 1));
		update(rt, 0, d - 1, e[i], dp[i] + c[i] * a);
	}
	cout << dp[n];
}