题意

公司有 $N$ 个员工，每个人会在 $0$ 时刻到 $M$ 时刻之间外出一次。公司的门在内部可以随意开关，在外面必须要钥匙才能开关。第 $i$ 个人会在 $S_i$ 时刻离开并在 $T_i$ 时刻返回，且他只能在这两个时刻开关门。$0$ 时刻门是关闭的。公司有 $K$ 把钥匙，将它们分配给其中 $K$ 个员工，要求每个人在返回时都能进入公司，最大化门关闭的时间。

限制

$1\le N\le 2000$, $1\le M\le 10^9$, $1\le K< N$, $0< S_i< T_i< M$，所有 $S_i$, $T_i$ 两两不相等。

题解

考虑每相邻两个事件 $(l, r)$ 之间是否关门：

• $(S_a,T_b)$：$a$ 和 $b$ 都有钥匙才能关门（$a=b$ 时就是 $a$ 有钥匙）；
• $(S_a,S_b)$：$a$ 有钥匙才能关门；
• $(T_a,T_b)$：$b$ 有钥匙才能关门；
• $(T_a,S_b)$：一定会关门。

把每个人看作一个点，选择每个点会贡献一个权值；同时存在若干条边，同时选择边的两个端点也会贡献一个权值。问题变为求解不超过 $K$ 个点的最大权导出子图。显然每个点的度不超过 $2$ 且无环，即图是若干条链。简单 DP 即可。

时间复杂度：$O(N^2)$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
constexpr int N = 2'000;
struct Event {
    int t, i, o;
    Event() = default;
    Event(int t, int i, int o) : t(t), i(i), o(o) {}
    friend bool operator<(const Event &lhs, const Event &rhs) {
        return lhs.t < rhs.t;
    }
};
int n, m, k, cnt;
Event event[2 * N + 2];
int val[N + 1], nxt[N + 1], vNext[N + 1], p[N + 1];
bool vis[N + 1];
int dp[2][N + 1][2];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m >> k;
    std::fill(nxt, nxt + n + 1, -1);
    event[cnt++] = {0, n, 0};
    event[cnt++] = {m, n, 1};
    for (int i = 0; i < n; ++i) {
        int s, t;
        std::cin >> s >> t;
        event[cnt++] = {s, i, 0};
        event[cnt++] = {t, i, 1};
    }
    std::sort(event, event + cnt);
    int ans = 0;
    for (int i = 0; i <= 2 * n; ++i) {
        auto &&[l, a, t0] = event[i];
        auto &&[r, b, t1] = event[i + 1];
        int t = 2 * t0 + t1, v = r - l;
        if (t == 0) {
            val[a] += v;
        } else if (t == 1) {
            if (a == b) {
                val[a] += v;
            } else {
                nxt[b] = a;
                vNext[b] = v;
                vis[a] = true;
            }
        } else if (t == 2) {
            ans += v;
        } else {
            val[b] += v;
        }
    }
    cnt = 0;
    for (int i = 0; i <= n; ++i)
        if (!vis[i])
            for (int j = i; j != -1; j = nxt[j])
                p[cnt++] = j;
    int cur = 0;
    for (int i = 0; i <= k + 1; ++i)
        dp[0][i][0] = dp[0][i][1] = -1;
    dp[0][1][1] = val[p[0]];
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        cur ^= 1;
        for (int j = 0; j <= k + 1; ++j)
            dp[cur][j][0] = dp[cur][j][1] = -1;
        for (int j = 0; j <= k + 1 && j <= i + 1; ++j)
            for (int x = 0; x <= 1; ++x)
                for (int y = 0; y <= 1; ++y)
                    if (j >= y && dp[cur ^ 1][j - y][x] != -1)
                        dp[cur][j][y] = std::max(dp[cur][j][y], dp[cur ^ 1][j - y][x] + y * val[p[i]] + x * y * vNext[p[i - 1]]);
    }
    std::cout << ans + dp[cur][k + 1][1] << "\n";
    return 0;
}