自动搬运

查看原文

来自洛谷，原作者为

	ShwStone 水出天际就叫水哥

搬运于2025-08-24 23:16:17，当前版本为作者最后更新于2025-05-18 23:16:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人题解。

这个题出的时候没想过还能三维偏序。我们先考察 $v = 1$ 的情况：将判定点画在 $xOt$ 平面上，从某个判定点出发，能到达的点的范围在它的左上 45 度到右上 45 度之间。

如下：

这是第一组样例对应的情况，如果判定了 F 点，下一步可判定的就是 A,B,C 之一。

这个画图似乎对解题没有帮助？并不！我们把整个图片旋转 45 度：

所以，此时每个点能到达的下一个点，就是位于右上方的点。这是一个“二维偏序最长链问题”，如果将所有点按照新的横坐标排序，就是在求新的纵坐标的最长不下降子序列。

形式化地，新的坐标是 $(t + x, t - x)$。

不过，完整的题目要考虑 $v$。所以实际上，一个点能到达的点是一个 $\pm \arctan(v)$ 的角度范围。以 $v=2$ 为例：

此时，我们在进行旋转运算的同时，还要向 t 轴方向做一个伸缩变换。感性理解，这两个变换显然不会改变可达点集。

形式话地说，得到的新坐标是 $(vt+x, vt-x)$，然后跑最长不下降子序列就好了。

题解 pdf 里那个证明更严谨一点。

代码：

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN(5e5 + 5);
 
struct Node {
    long long ta, tb;
};
 
int n;
long long v;
Node a[MAXN], len[MAXN];
 
bool operator<(Node x, Node y) {
    return x.ta != y.ta ? x.ta < y.ta : x.tb < y.tb;
}
 
bool compare(Node x, Node y) {
    return x.tb != y.tb ? x.tb < y.tb : x.ta < y.ta;
}
 
void solve() {
    scanf("%d %lld", &n, &v);
    for (int i = 1; i <= n; i++) {
        long long t, x;
        scanf("%lld %lld", &t, &x);
        a[i].ta = v * t + x;
        a[i].tb = v * t - x;
    }
    sort(a + 1, a + n + 1, compare);
    int ans = 0;
    len[0].ta = len[0].tb = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(len, len + ans + 1, a[i]) - len;
        len[p] = a[i];
        if (p > ans) ans++;
    }
    printf("%d\n", ans);
}
 
int main() {
    int _;
    scanf("%d", &_);
    while (_--) {
        solve();
    }
    return 0;
}