作为 NOIP 的第三题,需要一个模拟退火题。
现在有 n 个区间 [li,ri] ,每个区间有个权值 wi 。我们把这 n 个区间当成 n 个点,如果两个区间它们之间有交(包括端点),那么我们就在这两个区间之间连边,形成了一个区间图。
现在希望你删除一些区间,使得每个连通块大小不超过 k 。输出删除区间最小的权值和。
第一行两个整数 n , k
接下来 n 行,每行三个整数 li , ri , wi 。
一个整数表示答案
5 2 1 4 1 3 6 2 5 8 5 7 10 2 9 12 1
3
一共 10 个测试点。
对于测试点 1,2,保证 n≤20
对于测试点 3,4 保证 n≤100
对于测试点 5,6 保证 n≤500
对于所有测试点,保证 1≤k≤n≤2500,1≤li≤ri≤10^9,1≤wi≤10^9