Paired Up (USACO Gold 2021 December)

首先我们看到，可以把牛按间隔大于 $K$ 的相邻牛分组，组和组之间是没关系的，所以问题可以对每个组单独解，再加起来。

观察“极大匹配”这个条件，可以看到，如果在一个组内，要组成极大匹配，要不全连起来，要不pair内部或之间最多隔一个不成对的牛，而且不匹配的牛之间距离都要大于 $K$ 。

情况1: T=1

要想让未配对和最小，那每组要不就是全部配对（偶数头牛），要不就是空一个牛（奇数头牛）。这个情况比较简单，找到符合条件且重量最小的牛就行了。

情况2: T=2

要让未配对和最大，则在每组中跑一个DP：

$dp[i]=\{s_1,s_2\}$ 前 $i$ 头牛的未成对和， $s_1$ 是未成对牛为偶数的结果， $s_2$ 是未成对牛为奇数的结果。
需要有 $s_1$ ， $s_2$ 的原因，是这样才有保证最后成对的牛是偶数只。
last是如果i不成对，那么 $<i$ 的最靠右的可以不成对的牛的下标。
dp[i].first = max(dp[i-1].first, dp[last][j-1] + y[i])。

以下程序是从大到小循环的，意思一样。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;  // 1e5
int T, K;   // K <= 1e9
int x[100005], y[100005];
ll ans;
const int INF = 1e9;
 
int solve(int *x, int *y, int n) {
    vector<pair<int, int>> dp(n + 1);
    dp[n] = {0, -INF};
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1];
        int ub = upper_bound(x, x+n, x[i] + K) - x;
        if (i == 0 || i == n - 1 ||
            x[i+1] - x[i-1] <= K || !(n - i & 1))
            dp[i].first = max(dp[i].first, dp[ub].second + y[i]);
        if (i == 0 || i == n - 1 ||
            x[i+1] - x[i-1] <= K || (n - i & 1))
            dp[i].second = max(dp[i].second, dp[ub].first + y[i]);
    }
    return (n & 1 ? dp[0].second : dp[0].first);
}
 
int main() {
    scanf("%d %d %d", &T, &n, &K);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &x[i], &y[i]);
    if (T == 1) {
        int j = 0;
        for(int i = 0; i < n; i++) {
            if (i == n-1 || x[i+1]-x[i] > K) {
                if ((i-j+1) % 2) {       // odd #, find smallest valid element
                    int mi = INF;
                    for (int k = j; k <= i; k++) {
                        if ((k-j) % 2 == 0 || (x[k+1]-x[k-1] <= K))
                            mi = min(mi, y[k]);
                    }
                    // printf("%d:%d = %d\n", j, i, mi);
                    ans += mi;
                }
                j = i+1;
            }
        }
    } else {    // 最大化未配对和
        int j = 0;
        for(int i = 0; i < n; i++) {
            if (i == n-1 || x[i+1]-x[i] > K) {
                // run j to i
                int res = solve(x+j, y+j, i-j+1);
                // printf("%d:%d = %d\n", j, i, res);
                ans += res;
                j = i+1;
            }
        }
    }
    printf("%lld", ans);
    return 0;
}