带权值区间选点问题。

给定 nn 个数权值 aia_imm 个区间 lil_i~rir_i

从这 nn 个数中选取若干个数,要求每个区间至少1个数并且总的权值和最小。

n105,m106n \leq 10^5, m \leq 10^6

求助!

1 条评论

  • @ 2021-09-27 06:50:57

    DP 吗,首先有包含关系的几个区间显然只有最小的区间有意义,把大的区间全部去掉,可以得到一个不互相包含的区间序列。按左端点排序后 DP 就可以了吧,毕竟这个时候选择一个点可以消除序列上一个区间内的所有区间。

    • 1