ABC457G

Register_int · 2026-05-09 21:44:54 · 题解

何意味？

相信大家都做过猫和老鼠，看到这种题就知道要把坐标系旋转四十五度了。然后每个机器人就变成了只能往上或往右走，建图后等价于求最小链覆盖。那求最长反链即最长下降子序列即可。时间复杂度 \mathcal{O}(n\log n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

int main() {
    scanf("%d", &n); vector<pair<int, int>> a;
    for (int i = 1; i <= n; i++) {
        int t, x; scanf("%d%d", &t, &x);
        a.emplace_back(t + x, t - x);
    }
    sort(a.begin(), a.end()); vector<int> dp;
    for (auto _ : a) {
        auto it = lower_bound(dp.begin(), dp.end(), -_.second);
        if (it == dp.end()) dp.emplace_back(-_.second);
        else *it = -_.second;
    }
    printf("%u", dp.size());
}