做法是否具有正确性
查看原帖
做法是否具有正确性
660816
Claire0918楼主2024/10/27 12:08

线段覆盖问题。先将线段以左端点为第一关键字,右端点为第二关键字均升序排序。

fif_i 为前 ii 条线段的答案,lil_i 为在线段 ii 前的首条与其不交的线段。

有转移 fi=minj=li+1i1{fj}+1f_i = min_{j = l_i + 1}^{i - 1}\{f_j\}+1。分别使用线段树维护 {li}\{l_i\}{fi}\{f_i\}

是否具有正确性?

2024/10/27 12:08
加载中...