题解：P16447 [XJTUPC 2026] ADOIAF

Jason20090916 · 2026-05-10 20:24:18 · 题解

首先可以注意到对答案有贡献时，两个时间点相差不超过 k。
其次思考数据范围小时，我们可以使用最正常的背包 dp，但在本题 O(nm) 会超时。
结合以上两个思考，我们只需要对判定点和按键时刻分别升序排序，在枚举判定点时，使用双指针的思想维护对答案有贡献的按键时刻，同时进行 dp 即可。
注意 dp 时如果判定点 t_i 和 t_{i - 1} 对应的按键时刻没有交集，要进行转移。 ::::success[Code]

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int MAXN = 1e5 + 9;
int n, m, k, l, r, ans, a[MAXN], b[MAXN], dp[MAXN];
int f(int x, int y) {
    return max(0ll, k * k - (a[x] - b[y]) * (a[x] - b[y]));
}
void solve() {
    ans = 0;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    for(int i = 1; i <= m; i++) dp[i] = 0;
    sort(a + 1, a + n + 1), sort(b + 1, b + m + 1);
    l = 1, r = 0;
    for(int i = 1; i <= n; i++) {
        int nl = l;
        while(r < m && b[r + 1] - a[i] <= k) r++;
        while(l < m && a[i] - b[l] >= k) l++;
        for(int j = nl; j <= r; j++) dp[j] = max(dp[j], dp[j - 1]);
        for(int j = r; j >= l; j--) dp[j] = max(dp[j], dp[j - 1] + f(i, j));
    }
    for(int i = 1; i <= m; i++) ans = max(ans, dp[i]);
    cout << ans << '\n';
    return;
}
int T;
signed main() {
    cin >> T;
    while(T--) solve();
    return 0;
}

::::