JOISC 2021 Day3 保镖

Day \(\mathbb{P}_1+\mathbb{P}_2+\mathbb{P}_3+\mathbb{P}_4+\mathbb{P}_5+\mathbb{P}_6\)。

放到二维平面上考虑，点 \((x,y)\) 表示 \(x\) 时刻在 \(y\) 位置上，那么第 \(i\) 顾客的路径可以看成起点为 \((t_i,a_i)\)，终点为 \((t_i+|b_i-a_i|,b_i)\) 的线段 \(P_i\)。

注意到一个保镖的最优策略中一定不会闲着不动，因为如果他此时正在保护一个人的话显然跟下去比不动更优；如果他此时没有保护一个人的话显然是去找下一个保护的人更优。所以保镖的路径形如若干斜率 \(1\) 或者 \(-1\) 形成的线段拼接起来的折线 \(Q_i\)。

考虑到一个保镖一旦离开了正在保护的人就再也追不上他了，那么保镖 \(i\) 保护顾客 \(j\) 时间为 \(P_j\) 和 \(Q_i\) 重合的线段在时间轴上的投影长度，也就是重合线段长度 \(l\) 的 \(\frac{1}{\sqrt 2}\)。考虑将坐标轴顺时针旋转 \(45\) 度再进行放缩，那么 \((x,y)\to (x-y,x+y)\)，此时重合线段长度 \(l'\) 为 \(\sqrt 2l\)，那么保护时间就是重合线段长度的 \(\frac{1}{2}\)，收益就变成了 \(\frac{c_i}{2}\cdot l'\)。于是令 \(c_i\gets c_i\cdot \frac{1}{2}\)。

于是问题转化成平面上有若干平行或垂直于坐标轴的直线 \(P_1,P_2,\cdots ,P_n\)，\(q\) 次询问，每次询问给出一个点 \((x,y)\)，每次只能向上/向右走单位距离，和 \(P_i\) 重合的长度为 \(L_i\)，收益为 \(c_i\cdot L_i\)，求总收益最大是多少。

所有顾客线段延长交叉起来会变成一个大小为 \(O(n\times n)\) 的网格图。考虑 \((x,y)\) 一定是先径直走到网格图的某条线上，沿着某条可能不完整的线再走到某个格点，最后再在格点之间移动。

对网格进行离散化之后容易 dp \(O(n^2)\) 预处理出 \(f_{i,j}\) 表示目前在网格上的 \((i,j)\) 点，对应坐标系中的 \((x_i,y_j)\) 点（\(1\le i\le m,1\le j\le k\)），只能向上/向右走，走下去的最大收益。然后假设 \((x,y)\) 向上走到了 \((x,y_j)\) 所在的一条边，再向右走到了第一个格点 \((x_i,y_j)\)，那么取经过 \((x,y_j)\) 的 \(c_i\) 最大的线段 \(L_i\)，收益就是 \(c_i(x_i-x)+f_{i,j}\)。

注意到经过 \((x,y_j)\) 的线段必定经过 \((x_i,y_j)\) 和 \((x_{i-1},y_j)\)，因为一条直线起码经过两个格点。所以记 \(v_{i,j}\) 为经过格点 \((x_i,y_j)\) 且 \((x_i,y_j)\) 不为其右端点的线段 \(P_i\) 中 \(c_i\) 的最大值，那么收益就是 \(v_{i-1,j}(x_i-x)+f_{i,j}\)。

注意到 \(x\) 固定时 \(x_i\) 为第一个大于 \(x\) 的格点横坐标，所以 \(i\) 是固定的，将 \(v_{i-1,j}\) 看作一条直线的斜率，\(f_{i,j}\) 看作截距，问题转化为求给定 \(k\) 条直线在 \(x_i-x\) 处的 \(y\) 坐标的最大值，离线下来李超树解决即可。

复杂度 \(O((n^2+q)\log n+q\log q)\)。