#P17823. [Ontak2022]COF
[Ontak2022]COF
题目描述
有 间会议室和 场会议。第 场会议的举行时间为闭区间 ,取消它需要支付 。
会议之间的冲突按以下规则定义:
- 时间区间有交集的两场会议冲突,即使只在一个端点相交也冲突。
- 如果存在一场会议同时与会议 、会议 冲突,则 也冲突。
第二条可以反复应用,因此冲突关系具有传递性。冲突的两场会议必须安排在不同会议室。你可以取消任意一些会议;取消后,按剩余会议重新确定冲突关系。
求使剩余会议能够安排在 间会议室中所需的最小取消费用。
输入格式
第一行两个整数 。接下来 行,每行三个整数 。
输出格式
输出最小取消费用。
数据范围
;;。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n≤16 | 6 |
| 2 | k=1 | 12 |
| 3 | 所有 wᵢ=1 | 22 |
| 4 | n≤250 | 16 |
| 5 | 无额外限制 | 44 |
样例 1
输入:
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
输出:
3
说明
样例可取消 [3,6] 和 [9,12],费用为3。剩余 [1,4] 与其他会议不再冲突,另外两场分别使用两间会议室。