Gym103627E - Yet Another Interval Graph Problem

#题面

#题目描述

You are given $N$ closed intervals. The $i$-th interval covers $[s_i, e_i]$ and has a positive integer weight $w_i$. Consider the undirected graph of $N$ vertices, where each vertex corresponds to an interval, and there exists an edge between two vertices if and only if the corresponding pair of intervals has a nonempty intersection. For a given list of intervals, we call this graph the interval graph.

Jaehyun wants the graph to not have a connected component of size greater than $K$. To accomplish this, he can delete zero or more intervals. Jaehyun is lazy, so over all possible ways to delete intervals, he will select the way that minimizes the weight of the intervals he has to delete. Print the weight of the deleted intervals after he has made sure all connected components of the interval graph have size at most $K$.

#输入格式

The first line contains two integers $N$ and $K$ ($1 \le K \le N \le 2500$).

Each of the next $N$ lines contains three integers $s_i, e_i, w_i$ ($1 \le s_i \le e_i \le 10^9$, $1 \le w_i \le 10^{9}$).

#输出格式

Output the sum of the weights of the deleted intervals after Jaehyun’s deletions.

#输入输出样例

样例输入 #1

5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1

样例输出 #1

3

样例解释 #1

One possible solution is to remove the second and fifth intervals.

#思路

有 $n$ 个区间 $[l_i, r_i]$，每个区间有个权值 $w_i$。将这 $n$ 个区间当成 $n$ 个点，如果两个区间它们之间有交（包括端点），那么就在这两个区间之间连边。现在需要删除一些区间，使得每个连通块大小不超过 $k$。输出删除区间最小的权值和。

可以发现，最后肯定是删除经过某些位置的所有区间。

设 $f_i$ 表示当前切到位置 $i$，然后枚举上⼀段切的位置 $j$，然后考虑 $[i, j]$ 之间的区间只保留价值最⼤的 $k$ 个，将其他的区间都删掉，但是复杂度是 $O(n^3 \log n)$ 级别的，无法通过本题。

考虑优化，可以从后往前枚举 $j$ 依次加入区间，然后用堆维护⼀下前 $k$ ⼤即可，时间复杂度 $O(n^2 \log n)$，可以通过本题。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <iostream>
#include <algorithm>
#include <iterator>
#include <queue>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2505;

int n, k, s[N], e[N], w[N];
long long f[N << 1], sum;
std::vector<int> nums;
std::vector<std::pair<int, int>> g[N << 1];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> e[i] >> w[i];

        nums.emplace_back(s[i]);
        nums.emplace_back(e[i]);
        sum += w[i];
    }

    std::sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

    for (int i = 1; i <= n; i++) {
        s[i] = std::distance(nums.begin(), std::lower_bound(nums.begin(), nums.end(), s[i])) + 1;
        e[i] = std::distance(nums.begin(), std::lower_bound(nums.begin(), nums.end(), e[i])) + 1;

        g[s[i]].emplace_back(e[i], w[i]);
    }

    for (int i = 1; i <= nums.size(); i++) {
        std::priority_queue<int, std::vector<int>, std::greater<>> q;
        long long res = 0;

        for (int j = i; j; j--) {
            for (auto e : g[j]) {
                if (e.first <= i) {
                    if (q.size() < k) {
                        q.emplace(e.second);
                        res += e.second;
                    } else if (q.top() < e.second) {
                        res += e.second - q.top();
                        q.pop();
                        q.emplace(e.second);
                    }
                }
            }

            f[i] = std::max(f[i], f[j - 1] + res);
        }
    }

    cout << sum - f[nums.size()] << endl;

    return 0;
}