BZOJ 1537
离线题库
洛谷 3431
给定平面上的 $k$ 个点 $(i, j)$,每个点有权值,求一条从 $(1, 1)$ 到 $(n, m)$ 的路径(只能沿正方向走),使得经过的点的权值和最大。$1 \leq i, j \leq n, m \leq 10^9, 1 \leq k \leq 10^5$。

题解

设 $f(i, j)$ 为走到 $(i, j)$ 时经过点权值和的最大值,$w(i, j)$ 为点 $(i, j)$ 的权值(未给出则为 $0$),显然有
$$f(i, j) = max\left \{f(i - 1, j), f(i, j - 1)\right \} + w(i, j)$$
这样的复杂度是 $O(nm)$ 的,无法通过。注意到 $k$ 很小,可以将给出的点按 $x$ 坐标从小到大排序来离散化。排序后的一系列点满足 $x$ 坐标递增,所以到一个点时的 $f$ 只会由之前的点转移而来,原方程 $$f(i) = max\left \{f(j) | x_j \leq x_i, y_j \leq y_i\right \} + w_i$$ 可写为
$$f(i) = max\left \{f(j) | j < i, y_j \leq y_i\right \} + w_i$$
这样总的复杂度为 $O(k^2)$,优于上一个算法,但仍无法通过本题。
考虑每次转移的过程。要找到 $(x_i, y_i)$ 左下方 $f(i)$ 值最大的点,是二维偏序问题,考虑用树状数组维护 $f(i)$。
用树状数组维护 $y$ 坐标 $1..m$ 的每个前缀 $1..y$ 中 $f(i)$ 的最大值 $max\left \{f(i) | 1 \leq y_i \leq y\right \}$。通过对 $y$ 坐标离散化,事实上只需维护 $1..k$ 的每个前缀 $1..i$ 的 $max\left \{f(j) | 1 \leq y_j \leq y_i\right \}$。按 $x_i$ 升序转移的过程中,保证了 $f(i)$ 从 $x$ 坐标更小的点转移来,因此转移合法,每次转移的复杂度为 $O(logk)$,算上离散化的 $O(klogk)$,总的复杂度仅为 $O(klogk)$。

代码

bzoj1537_2dpo_bit.cpp