[ABC134E] Sequence Decomposing

Sequence Decomposing の 传送门

前置知识

multiset

Description

求一个数列 \(a\) 中递增子序列的最少个数。

Solution

考虑用 multiset 存每个递增子序列的最后一个数。

对于每一个 \(a_i\)(\(1\le i\le n\))，二分查找 multiset 中第一个小于 \(a_i\) 的数。

1. 如果有，就删除这个数，再放入 \(a_i\)。

2. 反之，就直接加入 \(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;
}