HBC213833排列,线段树,组合数学,树状数组,分治,排列组合,数据结构[网络流24题]最长k可重区间集问题题解（开区间集合i的最长k）

季陌殇算法基础篇 2023-11-09 17:08:02 43 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

给定实直线L 上n 个开区间组成的集合I，和一个正整数k，试设计一个算法，从开区间集合I 中选取出开区间集合SISsubseteq ISI，使得在实直线L 的任何一点x，S 中包含点x 的开区间个数不超过k，且∑z∈S∣z∣sum_{zin S}|z|∑z∈S∣z∣达到最大，这样的集合S称为开区间集合I的最长k可重区间集， ∑z∈S∣z∣sum_{zin S}|z|∑z∈S∣z∣称为最长k可

给定实直线L 上n 个开区间组成的集合I，和一个正整数k，试设计一个算法，从开区间集合I 中选取出开区间集合S⊆ISsubseteq IS⊆I，使得在实直线L 的任何一点x，S 中包含点x 的开区间个数不超过k，且∑z∈S∣z∣sum_{zin S}|z|∑z∈S∣z∣达到最大。这样的集合S称为开区间集合I的最长k可重区间集。 ∑z∈S∣z∣sum_{zin S}|z|∑z∈S∣z∣称为最长k可重区间集的长度。任务：对于给定的开区间集合I和正整数k，计算开区间集合I的最长k可重区间集的长度。