#768. #6014. 「网络流 24 题」最长 k 可重区间集

#6014. 「网络流 24 题」最长 k 可重区间集

题目描述

给定实直线 LL 上 nn 个开区间组成的集合 II,和一个正整数 kk,试设计一个算法,从开区间集合 II 中选取出开区间集合 S⊆IS \subseteq I,使得在实直线 LL 的任何一点 xx,SS 中包含点 xx 的开区间个数不超过 kk。且 ∑z∈S∣z∣\sum\limits_{z \in S} | z | 达到最大。这样的集合 SS 称为开区间集合 II 的最长 kk 可重区间集。∑z∈S∣z∣\sum\limits_{z \in S} | z | 称为最长 kk 可重区间集的长度。 对于给定的开区间集合 II 和正整数 kk,计算开区间集合 II 的最长 kk 可重区间集的长度。

输入格式

文件的第 11 行有 22 个正整数 nn 和 kk,分别表示开区间的个数和开区间的可重迭数。
接下来的 nn 行,每行有 22 个整数 lil_i 和 rir_i,表示开区间的左右端点坐标,注意可能有 li>ril_i \gt r_i,此时请将其交换。

输出格式

输出最长 kk 可重区间集的长度。

4 2
1 7
6 8
7 10
9 13
15

数据范围与提示

1≤n≤500,1≤k≤31 \leq n \leq 500, 1 \leq k \leq 3