题解：P7987 [USACO21DEC] Paired Up G

Louis_lxy · 2025-06-14 11:01:12 · 题解

考虑定义 f(i,0/1) 表示前 i 个数，没选的数的个数的奇偶性是 0/1 的方案数。

解释一下定义，显然我们要讨论当前考虑的奶牛是跟前面一个配对还是后面的配对，而这样定义可以简化转移，当然你也可以设前 i 个数选的数的奇偶性。于是就有了第二维。

考虑转移：

• 若第 i 头奶牛选择。
  • 若第 i 头是第偶数头，也就是它是跟前一头奶牛配对。注意到它要么跟 i-2 头配对，要么跟 i-1 头配对。注意到如果跟 i-2 头配对，那么第 i-1 头没有选择，而若 i-1 头没有选择，那么第 i-2 一定要跟 i 配对，这个在后面处理即可，于是我们只需要判断有没有可能跟 i-1 配对即可（若能跟 i-1 配对，那么 i-2 显然也能）。
  • 若第 i 头是奇数头，那么它是跟后面的配对，于是我们只需要考虑它是跟 i+1 还是 i+2 配对即可，注意到如果它跟 i+2 配对，那么 i-1 没有选择，而前文已经说了后面处理这种情况，于是仍然只需要讨论是不是跟 i+1 配对。
• 若第 i 头不选择，那么前面所有距离 i 超过 K 的都可以随便选。中间这部分一定都要选，考虑有没有可能成立。
  • 若第 i-1 头是偶数头，那么第 i-1 头一定要跟 i-2 头或者 i-3 头配对（不用考虑 i-3 理由同上），除非 i-1 不能与 i 配对，注意到如果 i-1 不能与 i-2 配对，那么 i-2 一定是上一个不能与 i 配对的数，那么注意到如果我们要选择偶数个数，那么不选 i 一定不优，所以可以不判，当然判了也没事。
  • 若第 i-1 头是奇数头，那么第 i-1 头一定要跟 i+1 头配对。

有了这些结论，推转移方程就不难了。

code：

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

const int N = 1e5 + 10;
int t, n, k, x[N], y[N], f[N][2];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t >> n >> k;
    if (t == 2) t = -1;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i], y[i] *= t;
    x[0] = -2e9, x[n + 1] = 2e9;
    memset(f, 63, sizeof f);
    f[0][0] = 0;
    for (int i = 1, lst = 0; i <= n; ++i) {
        while (x[i] - x[lst + 1] > k) ++lst;
        int id = i & 1;
        if (x[i] - x[i - 1] <= k) f[i][id] = min(f[i][id], f[i - 1][id]);
        if (x[i + 1] - x[i] <= k) f[i][id ^ 1] = min(f[i][id ^ 1], f[i - 1][id ^ 1]);
        f[i][id] = min(f[i][id], f[lst][id ^ 1] + y[i]);
        if (x[i + 1] - x[i - 1] <= k) f[i][id ^ 1] = min(f[i][id ^ 1], f[lst][id] + y[i]);
    }
    cout << abs(f[n][n & 1]);
    return 0;
}

后记：做题一定要看数据范围，注意到这个 dp 成立的条件是 K>0，可以自己想想为什么。