姉の彼女にキスをした

宝宝题。

首先暴力 dp。把起点和终点放在

T_0

和

T_{n+1}

，记

f_i

表示不停跳直到到达

T_i

休息，此时体力最大值。枚举上一个休息位置

j

，中间为了减少损耗一定尽量少跳，转移

f_i\gets B_i+f_j-A\left\lceil\dfrac{T_i-T_j}{D}\right\rceil

。暴力做到

O(n^2)

。

考察后面的上取整，注意到：

\left\lceil\dfrac{a-b}{D}\right\rceil=\left\lfloor\dfrac{a}{D}\right\rfloor-\left\lfloor\dfrac{b}{D}\right\rfloor+[a\bmod D \ge b\bmod D]

其中

a

已经确定是

P_i

，最大化后面有关

b

的下取整以及艾弗森括号。于是我们转移的同时维护

t_x

表示

P_i\equiv x\pmod D

对应的

F_i+A\left\lfloor\dfrac{P_i}{D}\right\rfloor

的

\max

。艾弗森括号在

x < a\bmod D

时不成立，大于时成立，对两种情况分别求出

t

的区间

\max

计算答案即可，支持单点 chkmax 区间最大值，动态开点线段树简单做到

O(n\log V)

。

CPP

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 1e5 + 10;
int n, P[N], Q[N], D, A;
LL F[N];

int ptot, rt, ls[N * 30], rs[N * 30]; LL tr[N * 30];
void update(int& p, int l, int r, int x, LL k) {
	if (!p) p = ++ ptot;
	if (l == r) { tr[p] = k; return ; }
	int mid = (l + r) >> 1;
	if (x <= mid) update(ls[p], l, mid, x, k);
	else update(rs[p], mid + 1, r, x, k);
	tr[p] = max(tr[ls[p]], tr[rs[p]]); return ;
}
LL query(int p, int l, int r, int x, int y) {
	if (!p || x > r || y < l) return -1e18;
	if (x <= l && y >= r) return tr[p];
	int mid = (l + r) >> 1;
	return max(query(ls[p], l, mid, x, y), query(rs[p], mid + 1, r, x, y));
}

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	tr[0] = -1e18;
	int s, t; cin >> s >> t >> D >> A >> n; P[0] = s, P[n + 1] = t;
	for (int i = 1; i <= n; i ++) cin >> P[i] >> Q[i];
	memset(F, -0x3f, sizeof F); F[0] = 0;
	update(rt, 0, D, P[0] % D, F[0] + 1ll * P[0] / D * A);
	for (int i = 1; i <= n + 1; i ++) {
		int p = P[i] % D;
		F[i] = Q[i] + max(query(rt, 0, D, 0, p - 1), query(rt, 0, D, p, D) + A) - 1ll * P[i] / D * A - A;
		update(rt, 0, D, p, F[i] + 1ll * P[i] / D * A);
	}
	cout << F[n + 1] << "\n";
	return 0;
}

姉の彼女にキスをした

文章操作

相关推荐

评论

姉の彼女にキスをした