题解：P16447 [XJTUPC 2026] ADOIAF

ShwStone · 2026-05-10 19:46:15 · 题解

出题人题解。

延续了去年的 L 题，依旧是音游背景的简单 DP。在赛时，正式队伍中只有冠军通过了此题。

题意：给定一个完全二分图，a_i 与 b_j 的边权是 \max(k^2 - (a_i - b_j)^2, 0)，求最大权匹配。k \le 50。

解题的关键是注意到，最终的匹配结果一定不存在两个非 0 的交叉匹配。假设 a_1 < a_2, b_1 < b_2，并且任意两个数距离不超过 k（有正边权），那么交叉匹配的收益如下：

而不交叉匹配的收益如下：

将两者做差，进行因式分解：

即不交叉匹配的收益一定更大。由此易知最终匹配中必然不存在交叉匹配。

有这个性质之后，就可以进行 DP 了。用 dp_{i,j} 表示只考虑 a 的前 i 个，b 的前 j 个点进行匹配的最大权，不难写出如下转移：

由于有 |a_i - b_{j'}| < k，并且 \{a_i\} 和 \{b_j\} 互不相同，所以 dp_i 相比 dp_{i - 1}，只有至多 2k 个值发生改变，因此可以开一个一维数组，每次只修改会变化的 dp 值。精细实现区间范围和前缀最大值维护可以做到 \mathcal O(nk)。

如果不想精细实现前缀最大值，将数组换成数状数组，也可以 \mathcal O(nk \log n) 通过此题。

std：

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN(5e5 + 5);

int n, m, k;
int a[MAXN], b[MAXN];
int dp[MAXN];

void solve() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= m; i++) scanf("%d", b + i);

    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);

    for (int i = 1; i <= m; i++) dp[i] = 0;

    int bl = 1, br = 1;
    for (int i = 1; i <= n; i++) {
        while (br <= m && b[br] <= a[i] + k) {
            dp[br] = max(dp[br], dp[br - 1]);
            br++;
        }
        while (bl < br && b[bl] < a[i] - k) bl++;

        auto score = [&](int j) -> int {
            int dis = a[i] - b[j];
            return max(k * k - dis * dis, 0);
        };

        for (int j = br - 1; j >= bl; j--) {
            dp[j] = max(dp[j], dp[j - 1] + score(j));
        }
        for (int j = bl; j < br; j++) {
            dp[j] = max(dp[j], dp[j - 1]);
        }
    }

    for (int i = 1; i <= m; i++) dp[i] = max(dp[i], dp[i - 1]);
    printf("%d\n", dp[m]);
}

int main() {
    int _;
    scanf("%d", &_);
    while (_--) solve();
    return 0;
}