前置知识
Description
求一个数列 \(a\) 中递增子序列的最少个数。
Solution
考虑用 multiset 存每个递增子序列的最后一个数。
对于每一个 \(a_i\)(\(1\le i\le n\))，二分查找 multiset 中第一个小于 \(a_i\) 的数。
-
如果有，就删除这个数，再放入 \(a_i\)。
-
反之，就直接加入 \(a_i\)。
Code
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
int cnt;
multiset<int> s;
signed main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (s.empty()) {
s.insert(a[i]);
continue;
}
multiset<int>::iterator k = s.lower_bound(a[i]);
if (k != s.begin()) {
--k;// 防止越界
if (a[i] > *k) {
//上升子序列
s.erase(k);
s.insert(a[i]);
}
}
else
s.insert(a[i]);
}
cout << s.size();
return 0;
}