#P17823. [Ontak2022]COF

    ID: 16766 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>动态规划贪心CF2100排序堆算法基础模拟

[Ontak2022]COF

题目描述

有 kk 间会议室和 nn 场会议。第 ii 场会议的举行时间为闭区间 [si,ei][s_i,e_i],取消它需要支付 wiw_i。

会议之间的冲突按以下规则定义:

  1. 时间区间有交集的两场会议冲突,即使只在一个端点相交也冲突。
  2. 如果存在一场会议同时与会议 ii、会议 jj 冲突,则 i,ji,j 也冲突。

第二条可以反复应用,因此冲突关系具有传递性。冲突的两场会议必须安排在不同会议室。你可以取消任意一些会议;取消后,按剩余会议重新确定冲突关系。

求使剩余会议能够安排在 kk 间会议室中所需的最小取消费用。

输入格式

第一行两个整数 n,kn,k。接下来 nn 行,每行三个整数 si,ei,wis_i,e_i,w_i。

输出格式

输出最小取消费用。

数据范围

1≤k≤n≤25001\le k\le n\le2500;1≤si≤ei≤1091\le s_i\le e_i\le10^9;1≤wi≤1091\le w_i\le10^9。

子任务

子任务 附加限制 分值
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] 与其他会议不再冲突,另外两场分别使用两间会议室。