如果 \(T = 1\)，可以把重量全部取相反数转化成 \(T = 2\)。接下来只考虑 \(T = 2\) 的情况。
下文的 \(m\) 代表原题中的 \(K\)。
设第 \(i\) 个 G 牛的位置和重量分别为 \(a_{0, i}, b_{0, i}\)，第 \(i\) 个 H 牛的位置和重量分别为 \(a_{1, i}, b_{1, i}\)。
考虑 dp。dp 状态的前两维一定是 \(i, j\) 表示当前考虑了前 \(i\) 个 G 牛和前 \(j\) 个 H 牛的匹配。为了使匹配极大，还需要多记一维上一个失配的牛，无法承受。
考虑改变 dp 状态的含义，设 \(f_{i, j, 0/1}\) 表示当前考虑了前 \(i\) 个 G 牛和前 \(j\) 个 H 牛的匹配，上一个失配的牛是第 \(i\) 个 G 牛或者第 \(j\) 个 H 牛。
考虑转移。以 \(f_{i, j, 0}\) 为例。枚举连续的匹配数 \(k\)，如果 \((i + 1, j + 1), (i + 2, j + 2), \ldots, (i + k, j + k)\) 都能形成匹配，那么 \(f_{i + k + 1, j + k, 0} \gets f_{i, j, 0} + b_{0, i + k + 1}\)。在此基础上，如果 \(a_{1, j + k + 1} > a_{0, i} + m\)，那么可以切换失配的牛的品种，即 \(f_{i + k, j + k + 1, 1} \gets f_{i, j, 0} + b_{1, j + k + 1}\)。\(f_{i, j, 1}\) 类似。然后我们可以 \(O(n)\) 地转移：
code
ll f[maxn][maxn][2];
void solve() {
mems(f, -0x3f);
f[0][0][0] = f[0][0][1] = 0;
for (int i = 0; i <= A; ++i) {
for (int j = 0; j <= B; ++j) {
for (int k = 0; i + k + 1 <= A && j + k <= B; ++k) {
if (k && abs(a[0][i + k] - a[1][j + k]) > m) {
break;
}
f[i + k + 1][j + k][0] = max(f[i + k + 1][j + k][0], f[i][j][0] + b[0][i + k + 1]);
if (a[0][i + k + 1] - a[1][j] > m && j) {
f[i + k + 1][j + k][0] = max(f[i + k + 1][j + k][0], f[i][j][1] + b[0][i + k + 1]);
}
}
for (int k = 0; i + k <= A && j + k + 1 <= B; ++k) {
if (k && abs(a[0][i + k] - a[1][j + k]) > m) {
break;
}
f[i + k][j + k + 1][1] = max(f[i + k][j + k + 1][1], f[i][j][1] + b[1][j + k + 1]);
if (a[1][j + k + 1] - a[0][i] > m && i) {
f[i + k][j + k + 1][1] = max(f[i + k][j + k + 1][1], f[i][j][0] + b[1][j + k + 1]);
}
}
}
}
printf("%lld\n", max(f[A][B][0], f[A][B][1]));
}
发现转移是把一条对角线取 \(\max\)。考虑类似差分，最后再前缀 \(\max\) 起来。以 \(f_{i, j, 0}\) 为例，可以选择让第 \(i + 1\) 个 G 牛失配，即 \(f_{i + 1, j, 0} \gets f_{i, j, 0} + b_{0, i + 1}\)；可以选择让第 \(i + 1\) 个 G 牛和第 \(j + 1\) 个 H 牛匹配，即 \(f_{i + 1, j + 1, 0} \gets f_{i, j, 0}\)；还要切换失配的牛的种类。找到最小的非负整数 \(k\) 使得 \(a_{1, j + k + 1} > a_{0, i} + m\)，若 \((i + 1, j + 1), (i + 2, j + 2), \ldots, (i + k, j + k)\) 都能匹配，那么 \(f_{i + k, j + k, 1} \gets f_{i, j, 0}\)。
容易合理地预处理做到时空复杂度均为 \(O(n^2)\)。
code
// Problem: P7985 [USACO21DEC] Paired Up P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7985
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
ll K, n, m, A, B, f[maxn][maxn][2], a[2][maxn], b[2][maxn];
int g[maxn][maxn], nxt[2][maxn];
inline void upd(ll &x, ll y) {
(y > x) && (x = y);
}
void solve() {
scanf("%lld%lld%lld", &K, &n, &m);
for (int i = 1, x, y; i <= n; ++i) {
char op[9];
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'G') {
a[0][++A] = x;
b[0][A] = y;
} else {
a[1][++B] = x;
b[1][B] = y;
}
}
if (K == 1) {
for (int i = 1; i <= A; ++i) {
b[0][i] = -b[0][i];
}
for (int i = 1; i <= B; ++i) {
b[1][i] = -b[1][i];
}
}
for (int i = A; i; --i) {
for (int j = B; j; --j) {
if (abs(a[0][i] - a[1][j]) <= m) {
g[i][j] = g[i + 1][j + 1] + 1;
}
}
}
for (int i = 1; i <= A; ++i) {
for (int j = 1; j <= B; ++j) {
if (a[1][j] > a[0][i] + m) {
nxt[0][i] = j;
break;
}
}
}
for (int j = 1; j <= B; ++j) {
for (int i = 1; i <= A; ++i) {
if (a[0][i] > a[1][j] + m) {
nxt[1][j] = i;
break;
}
}
}
mems(f, -0x3f);
f[0][0][0] = f[0][0][1] = 0;
for (int i = 0; i <= A; ++i) {
for (int j = 0; j <= B; ++j) {
int k = max(nxt[1][j] - i - 1, 0);
if (nxt[1][j] && k <= g[i + 1][j + 1] && j) {
upd(f[i + k][j + k][0], f[i][j][1]);
}
k = max(nxt[0][i] - j - 1, 0);
if (nxt[0][i] && k <= g[i + 1][j + 1] && i) {
upd(f[i + k][j + k][1], f[i][j][0]);
}
upd(f[i + 1][j][0], f[i][j][0] + b[0][i + 1]);
upd(f[i][j + 1][1], f[i][j][1] + b[1][j + 1]);
if (abs(a[0][i + 1] - a[1][j + 1]) <= m) {
upd(f[i + 1][j + 1][0], f[i][j][0]);
upd(f[i + 1][j + 1][1], f[i][j][1]);
}
}
}
printf("%lld\n", K == 1 ? -max(f[A][B][0], f[A][B][1]) : max(f[A][B][0], f[A][B][1]));
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}