10.18 CSP-S模拟赛

T1

只考虑连

a_u \leq a_v

的边，把所有边按照边权从小到大排序，跑一遍 dfs 求出最长路即可。

你发现这种要求满足限制的题，且可以通过

x_r - x_l = d_i

构造关系。直接考虑差分约束，如果说出现当前

u,v

距离与之前所求矛盾则无解。根据

\begin{cases}x_r - x_l \leq d_i \\ x_l - x_r \leq -d_i\end{cases}

建边。

首先所有被其它区间完全覆盖的区间一定是要删的。

将所有线段左端点第一关键字右端点第二升序排序，考虑 dp。记

f_{i,j}

表示前

i

个中选了

j

个删除，钦定

i

不删的最长区间覆盖。转移枚举上一个没删的区间。

f_{i,j} = \max\limits_{k < i}\{f_{k,j - (i - k - 1)} + r_i - \max(l_i,r_k)\}

显然我们需要分讨后面的

\max

。

$l_i > r_k$

那么有 $f_{i,j} = \max\limits_{k<i}\{f_{k,k - (i - j - 1)} + r_i - l_i\}$ ，那么我们只需要知道 $f_{k,k - (i - j - 1)}$ 对于每个 $i - j - 1$ 的最大值即可。
$l_i < r_k$

那么有 $f_{i,j} = \max\limits_{k<i}\{f_{k,k - (i - j - 1)} + r_i - r_k\}$ ，同理的我们需要维护 $f_{k,k - (i-j-1)} - r_k$ 的最大值。

那么只需要单调队列维护第二种情况的同时更新第一种即可。