算法
(染色问题、双端队列、二分) $O(N\log N)$
只需求出最长非上升子序列的长度即可,因为对每个严格上升子序列都可以染同一种颜色。
具体实现:
可以开双端队列 std::deque
来维护当前非上升子序列的元素,对每个 $a_i$,可以先在双端队列中找出大于等于 $a_i$ 的第一个元素的位置 $p$,可以用双端队列自带的 lower_bound
函数来找,若 $p$ 为 $0$($a_i$ 小于等于当前双端队列中的最小元素),则在双端队列的最左端插入 $a_i$,反之若 $p$ 不为 $0$($a_i$ 比当前双端队列中 $p$ 位置左边的所有数都大),将双端队列中 $p - 1$ 位置的数改成 $a_i$。最后双端队列的大小就是答案。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::deque;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
deque<int> d;
rep(i, n) {
int p = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
if (p == 0) {
d.push_front(a[i]);
}
else d[p - 1] = a[i];
}
int ans = d.size();
cout << ans << '\n';
return 0;
}