题解：P14410 [JOISC 2015] 钥匙 / Keys

· · 题解

好题！好可爱的题！

但是代码细节害死人。min(i, sz) 写成 i 直接 100 \to 10。

依旧先考虑钦定了哪些人拿钥匙之后，会产生哪些贡献。

定义一个员工进或者出为一个事件。

不难发现，事件和两端的边界，把整个区间划分成了若干个时间段。

::::info[image] ::::

对于一个时间区间 [L,R]，考虑两端的事件情况，可以知道，该区间是否能够贡献，只取决于两端事件情况。

::::info[image] ::::

注意到，一个区间是否能够贡献，只取决于“左端点是否是无钥匙的人离开”以及“右端点是否是无钥匙的人返回”。

所以一个区间想要贡献，可能会对两端的人产生要求：

考虑如何刻画后两个限制，考虑建图。

令左侧的人为 u，右侧的人为 v，区间长度贡献为 w = R - L，则可能出现以下三种情况需要额外代价：

那么原问题等价于，在这样一张图上，可以选择 k 个点，要使得这 k 个点的点权之和加边权之和最大。

注意到，图上不可能存在环，也不可能存在度数超过 2 的点。换句话说，整个图就是由若干个不相交的链组成的。

那么我们可以先在链上 DP，用 dp_{i,j,0/1} 表示考虑到了点 i，目前选了 j 个点，是否选择 i 的最大贡献。令链的长度为 l，在链上 DP 的复杂度是 O(l^2) 的。转移的 trivial 的，不赘述。

每次 DP 完一个链之后，将其答案做背包装物合并进答案 f 中。f_{i} 表示选择 i 个点所能得到的最大贡献。转移也是 trivial 的，不过要注意精细实现，每个链能取的点数不会超过链长 l。若不精细实现，复杂度将会变成 O(nk^2) 而不是 O(nkl)。

由于 l 之和小于等于 n，所以总复杂度大概是 O(nk) 级别的，考虑到 n,k \leq 2000，完全可以通过。

代码并不是很好写，具体的转移和实现见代码。

::::success[Code]

#include <bits/stdc++.h>
#define For(i, j, k) for (int i = j; i <= k; ++ i)
#define Rof(i, j, k) for (int i = j; i >= k; -- i)
#define eb emplace_back
using namespace std;
using ll = long long;
using db = double;
using vi = vector<int>;
using p2 = array<int, 2>;
using p3 = array<int, 3>;
const int N = 2e3 + 10, inf = 0x3f3f3f3f;
int n, m, k, s[N], t[N], n1 = 0, w[N], ans = 0;
int dp[N][N][2], f[N], tmp[N], deg[N];
p3 a[N * 2];
vector<p2> g[N];
bool vis[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    For (i, 1, n) cin >> s[i] >> t[i];
    a[ ++ n1] = {0, 1, 0};
    For (i, 1, n) {
        a[ ++ n1] = {s[i], 0, i};
        a[ ++ n1] = {t[i], 1, i};
    }
    a[ ++ n1] = {m, 0, 0};
    sort(a + 1, a + 1 + n1);
    f[0] = 0; For (i, 1, k) f[i] = -inf;
    For (i, 1, n1 - 1) {
        auto [L, idl, id1] = a[i];
        auto [R, idr, id2] = a[i + 1];
        int tw = R - L;
        if (idl == 0 && idr == 1 && id1 != id2) {
            g[id1].eb((p2){id2, tw});
            g[id2].eb((p2){id1, tw});
            deg[id1] ++, deg[id2] ++ ;
        }
        else if (idl == 0) w[id1] += tw;
        else if (idr == 1) w[id2] += tw;
        else ans += tw;
    }
    For (st, 1, n) {
        if (vis[st] || deg[st] > 1) continue;
        int sz = 0;
        if (deg[st] == 0) {
            vis[st] = 1;
            For (i, 0, k) tmp[i] = -inf;
            tmp[0] = 0, tmp[1] = w[st], sz = 1;
        }
        else{
            queue<int> q; q.push(st);
            vis[st] = 1;
            vi lnk;
            For (i, 0, k) dp[st][i][0] = dp[st][i][1] = -inf;
            dp[st][0][0] = 0;
            dp[st][1][1] = w[st];
            int ed = st; sz = 1;
            while (q.size()) {
                int u = q.front(); q.pop(); ed = u;
                for (auto [v, tw] : g[u]) {
                    if (vis[v]) continue;
                    vis[v] = 1; q.push(v); sz ++ ;
                    For (i, 0, k) dp[v][i][0] = dp[v][i][1] = -inf;
                    For (i, 0, k) {
                        dp[v][i][0] = max(dp[u][i][0], dp[u][i][1]);
                        if (i > 0 && dp[u][i - 1][0] != -inf)
                            dp[v][i][1] = max(dp[v][i][1], dp[u][i - 1][0] + w[v]);
                        if (i > 0 && dp[u][i - 1][1] != -inf)
                            dp[v][i][1] = max(dp[v][i][1], dp[u][i - 1][1] + tw + w[v]);
                    }
                }
            }
            For (i, 0, k) tmp[i] = max(dp[ed][i][0], dp[ed][i][1]);
        }
        Rof (i, k, 0) For (j, 0, min(i, sz)) f[i] = max(f[i], f[i - j] + tmp[j]);
    }
    cout << ans + f[k] << '\n';
    return 0;
}

::::