CF559E Gerald and Path

题意

$n$ 根线段，已知其中一个端点和长度，求最长覆盖

题解

等价于每根线段要么不选，要么取一段前缀，要求两两无交，求最长覆盖

按已知端点排序，$f_{i,j}$ 表示前 $i$ 条线段，被覆盖的最靠右的点在 $j$ 或 $j$ 左侧的最长覆盖
$p_i$ 是已知端点，$l_i$ 是向左的另一个端点，$r_i$ 是向右的另一个端点

• $i$ 不选
  $f_{i,j}\leftarrow f_{i-1,j}$
• $i$ 向右
  如果 $i$ 左边的线段在 $r_i$ 右边有贡献，那么不如不选 $i$
  也就是 $i$ 直接接在最后
  即 $\forall j\in[p_i,r_i],f_{i,j}\leftarrow f_{i-1,p}+\text{dist}(p_i,j)$
• $i$ 向左
  如果线段 $m$ 在 $l_i$ 左边有贡献，$n(n\le m)$ 在 $p_i$ 右边有贡献，那么 $i$ 向右肯定不劣于向左
  于是可以枚举线段 $k\left(k\in[1,i),p_k>l_i\right)$，$1\dots k-1$ 算 $l_i$ 左边的贡献，$k\dots i-1$ 全部向右
  即令 $R=\max\{p_i,\max\limits_{k\le j<i}r_j\}$，$\forall j\in[l_i,R],f_{i,j}\leftarrow f_{k-1,l_i}+\text{dist}(l_i,j)$
  这一块可以优化到单行 $\Theta(n)$，详见代码

最后，根据定义，$f_{i,j}\leftarrow \min\limits_{1\le k\le j}f_{i,k}$

总共 $\Theta(n^2)$

codeforces submission 155923484