【排序、DP】ABC439E
WanderOvO
·
·
题解
【排序、DP】ABC439E
原题链接
简要题意
编号为 1 至 N 的 N 人正在河边放风筝。考虑一个二维坐标系，x 轴为河水方向，y 轴为高度方向。
第 i 个人站在点 (A_i, 0) 上，试图在点 (B_i, 1) 上放风筝。
但是，为了避免人与风筝发生碰撞，也为了避免风筝线缠绕在一起，如果满足以下条件，i 和 j（i \neq j）就不能同时放风筝：
- 连接 (A_i, 0) 和 (B_i, 1) 的线段，和连接 (A_j, 0) 和 (B_j, 1) 的线段有一个交点。(包括线段的端点相互接触的情况）。
在遵守上述限制的前提下，最多可以同时放风筝的人数是多少？
## 思路
我们不妨先把所有人按照 $a_i$ 升序排序，则会发现，其实就是从左到右选择一些人，使得他们的 $a_i$ **严格单调递增**，且 $b_i$ **严格单调递增**，这样才没有交点。所以这个题其实就是一个变种的最长上升子序列问题。
现在 $a_i$ 已经**单调不减**了，我们接下来要保证从左到右选的 $a_i$ 严格单调递增且 $b_i$ 严格单调递增。
为了排除掉相等带来的问题，我们发现在按照 $a_i$ 为第一关键字升序排序时，把 $b_i$ 作为第二关键字**降序排序**，这样只需要求 $b_i$ 的最长严格上升子序列，就能同时保证 $a_i$ 也是严格单调递增的。
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
void solve() {
int n;
cin >> n;
vector<PII> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a.begin() + 1, a.end(), [&] (const PII &o1, const PII &o2) {
if (o1.first == o2.first) {
return o1.second > o2.second;
}
return o1.first < o2.first;
});
vector<int> dp;
for (int i = 1; i <= n; i++) {
int val = a[i].second;
auto it = lower_bound(dp.begin(), dp.end(), val);
if (it == dp.end()) {
dp.push_back(val);
} else {
*it = val;
}
}
cout << dp.size() << "\n";
}
int main() {
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
```