无环等价于每个点至多被两个区间覆盖,求最大的权值和。这是一个经典问题,可以用最小费用流解决:
- 对每个区间,从 $s_i-1$ 到 $e_i$ 连边容量 $1$,费用 $-w_i$。
- 对每个 $x\pod{0\le x<\max\{e_i\}}$,从 $x$ 到 $x+1$ 连边容量 $+\infty$,费用 $0$。
从 $0$ 到 $\max\{e_i\}$ 的流量为 $2$ 的最小费用流的相反数即为答案。注意初始时图中有负边,但是是 DAG,在使用 Dijkstra 算法时将点 $u$ 的势能设为 $-10^{12}\cdot u$ 即可。
时间复杂度 $O(N\log N)$。