Problem
洛谷 P7987 [USACO21DEC] Paired Up G
题目大意：
有 \(n\) 个点，其中第 \(i\) 个点位置为 \(x_i\)，权值为 \(y_i\)。若两个点 \(i, j\) 满足 \(|x_i - x_j| \le k\)，则这两个点之间有一条边。
求一个匹配，在满足其为极大匹配的情况下匹配点的权值和最大/最小。
求总权值和与匹配点的权值和的差。
Solution
提供一种不同于洛谷题解区的解法。
结论：作为答案的匹配中的任意两对匹配 \((a, b)\) 和 \((c, d)\)，区间 \([a, b]\) 与区间 \([c, d]\) 一定不交。
这个可以用调整法证明。如果两个匹配 \((a, b)\) 和 \((c, d)\) 满足 \(a < c < b < d\)，则可以将匹配调整成 \((a, c)\) 和 \((b, d)\)。
如果两个匹配 \((a, b)\) 和 \((c, d)\) 满足 \(a < c < d < b\)，则匹配可以调整成 \((a, c)\) 和\((d, b)\)。
于是我们可以得到另一个结论：一个点只会与其前两个点或后两个点匹配。
因为如果某个点 \(i\) 与 \(i - 3\) 匹配，则 \(i - 2\) 和 \(i - 1\) 必然会成为匹配点。此时不满足区间无交。
于是我们就可以 \(\verb|dp|\) 了：设 \(dp_{i, 0 / 1 / 2}\) 表示只考虑前 \(i\) 个点，第 \(i\) 个点不在匹配中或与 \(i - 1\) 匹配或与 \(i - 2\) 匹配时的答案。
考虑转移。
我们不妨设 \(l_i\) 为第一个与 \(i\) 有边的节点。显然 \(1 \sim i - 1\) 中有且仅有 \(l_i \sim i - 1\) 与 \(i\) 有边。
\(l_i\) 可以双指针求出。
对于 \(dp_{i, 0}\)：
- 若 \(x_i - x_{i - 1} > k\)，则 \(i - 1\) 无论是什么状态都是合法的。
- 否则，必须满足 \(1 \sim i - 1\) 中所有与 \(i\) 有边的点都必须是匹配点。
- 如果这些点的个数为偶数，因为每个点只能与前后四个匹配，且区间无交，且每个点都要是匹配点，所以只能相邻两个匹配。
- 如果这些点的个数为奇数，依然相邻两个匹配，且最前面那个要与另外的点匹配。
所以有：
\[dp_{i, 0} = \left\{
\begin{array}{ll}
\min/\max(dp_{i - 1, 0}, dp_{i - 1, 1}, dp_{i - 1, 2}) & x_i - x_{i - 1} > k \\
\min/\max(dp_{l_i - 1, 0}, dp_{l_i - 1, 1}, dp_{l_i - 1, 2}) + \sum\limits_{j = l_i}^{i - 1} y_j & x_i - x_{i - 1} \le k, i - l_i \equiv 0 \pmod{2} \\
\min/\max(dp_{l_i, 1}, dp_{l_i, 2}) + \sum\limits_{j = l_i + 1}^{i - 1} y_j & x_i - x_{i - 1} \le k, i - l_i \equiv 1 \pmod{2}
\end{array}
\right.
\]
对于 \(dp_{i, 1}\)，当且仅当 \(x_i - x_{i - 1} \le k\) 时才能转移，且 \(i - 2\) 无论时什么状态都是合法的。
所以有：
\[dp_{i, 1} = \left.
\begin{array}{ll}
\min/\max(dp_{i - 2, 0}, dp_{i - 2, 1}, dp_{i - 2, 2}) + y_{i - 1} + y_i & x_i - x_{i - 1} \le k
\end{array}
\right.
\]
对于 \(dp_{i, 2}\)：首先必须满足 \(x_i - x_{i - 2} \le k\)。
然后需要满足 \(i - 1\) 无法匹配，这里的分析与 \(dp_{i, 0}\) 类似，不再赘述。
\[dp_{i, 2} = \left\{
\begin{array}{ll}
\min/\max(dp_{i - 3, 0}, dp_{i - 3, 1}, dp_{i - 3, 2}) & x_i - x_{i - 2} \le k, x_{i - 1} - x_{i - 3} > k \\
\min/\max(dp_{l_{i - 1} - 1, 0}, dp_{l_{i - 1} - 1, 1}, dp_{l_{i - 1} - 1, 2}) + \sum\limits_{j = l_{i - 1}}^{i - 2} y_j + y_i & x_i - x_{i - 2} \le k, x_{i - 1} - x_{i - 3} \le k, i - 2 - l_{i - 1} \equiv 0 \pmod{2} \\
\min/\max(dp_{l_{i - 1}, 1}, dp_{l_{i - 1}, 2}) + \sum\limits_{j = l_{i - 1} + 1}^{i - 2} y_j + y_i & x_i - x_{i - 2} \le k, x_{i - 1} - x_{i - 3} \le k, i - 2 - l_{i - 1} \equiv 0 \pmod{2}
\end{array}
\right.
\]
然后这题就做完了。
Code
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int t, n, k, x[100005], y[100005], l[100005];
long long sum[100005], dp[100005][3];
int main() {
scanf("%d%d%d", &t, &n, &k);
for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]), sum[i] = sum[i - 1] + y[i];
for (int ri = 1, le = 1; ri <= n; ri++) {
while (x[ri] - x[le] > k) le++;
l[ri] = le;
}
if (t == 1) {
long long inf = ~0x3f3f3f3f3f3f3f3f;
memset(dp, ~0x3f, sizeof(dp));
dp[0][0] = 0;
dp[1][0] = 0;
if (x[2] - x[1] > k) dp[2][0] = 0;
else dp[2][1] = y[1] + y[2];
if (x[3] - x[2] > k) dp[3][0] = max(dp[2][0], dp[2][1]);
else {
dp[3][0] = dp[2][1];
dp[3][1] = y[2] + y[3];
if (x[3] - x[1] <= k) dp[3][2] = y[1] + y[3];
}
for (int i = 4; i <= n; i++) {
if (x[i] - x[i - 1] > k)
dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
else if ((i - l[i]) % 2 == 0)
dp[i][0] = max({dp[l[i] - 1][0], dp[l[i] - 1][1], dp[l[i] - 1][2]}) +
sum[i - 1] - sum[l[i] - 1];
else dp[i][0] = max(dp[l[i]][1], dp[l[i]][2]) + sum[i - 1] - sum[l[i]];
if (x[i] - x[i - 1] <= k)
dp[i][1] = max({dp[i - 2][0], dp[i - 2][1], dp[i - 2][2]}) + y[i - 1] + y[i];
if (x[i] - x[i - 2] <= k) {
if (x[i - 1] - x[i - 3] > k)
dp[i][2] = max({dp[i - 3][0], dp[i - 3][1], dp[i - 3][2]}) + y[i - 2] + y[i];
else if ((i - 2 - l[i - 1]) % 2 == 0)
dp[i][2] =
max({dp[l[i - 1] - 1][0], dp[l[i - 1] - 1][1], dp[l[i - 1] - 1][2]}) +
sum[i - 2] - sum[l[i - 1] - 1] + y[i];
else dp[i][2] = max(dp[l[i - 1]][1], dp[l[i - 1]][2]) +
sum[i - 2] - sum[l[i - 1]] + y[i];
}
if (dp[i][0] < 0) dp[i][0] = inf;
if (dp[i][1] < 0) dp[i][1] = inf;
if (dp[i][2] < 0) dp[i][2] = inf;
}
printf("%lld\n", sum[n] - max({dp[n][0], dp[n][1], dp[n][2]}));
} else {
long long inf = 0x3f3f3f3f3f3f3f3f;
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
dp[1][0] = 0;
if (x[2] - x[1] > k) dp[2][0] = 0;
else dp[2][1] = y[1] + y[2];
if (x[3] - x[2] > k) dp[3][0] = min(dp[2][0], dp[2][1]);
else {
dp[3][0] = dp[2][1];
dp[3][1] = y[2] + y[3];
if (x[3] - x[1] <= k) dp[3][2] = y[1] + y[3];
}
for (int i = 4; i <= n; i++) {
if (x[i] - x[i - 1] > k)
dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
else if ((i - l[i]) % 2 == 0)
dp[i][0] = min({dp[l[i] - 1][0], dp[l[i] - 1][1], dp[l[i] - 1][2]}) +
sum[i - 1] - sum[l[i] - 1];
else dp[i][0] = min(dp[l[i]][1], dp[l[i]][2]) + sum[i - 1] - sum[l[i]];
if (x[i] - x[i - 1] <= k)
dp[i][1] = min({dp[i - 2][0], dp[i - 2][1], dp[i - 2][2]}) + y[i - 1] + y[i];
if (x[i] - x[i - 2] <= k) {
if (x[i - 1] - x[i - 3] > k)
dp[i][2] = min({dp[i - 3][0], dp[i - 3][1], dp[i - 3][2]}) + y[i - 2] + y[i];
else if ((i - 2 - l[i - 1]) % 2 == 0)
dp[i][2] =
min({dp[l[i - 1] - 1][0], dp[l[i - 1] - 1][1], dp[l[i - 1] - 1][2]}) +
sum[i - 2] - sum[l[i - 1] - 1] + y[i];
else dp[i][2] = min(dp[l[i - 1]][1], dp[l[i - 1]][2]) +
sum[i - 2] - sum[l[i - 1]] + y[i];
}
if (dp[i][0] > inf) dp[i][0] = inf;
if (dp[i][1] > inf) dp[i][1] = inf;
if (dp[i][2] > inf) dp[i][2] = inf;
}
printf("%lld\n", sum[n] - min({dp[n][0], dp[n][1], dp[n][2]}));
}
return 0;
}