POJ 3903 - Stock Exchange

http://poj.org/problem?id=3903

概要

L 個の要素からなる数列 p[i] が与えられ， p[i[1]] < p[i[2]] < ... < p[i[k]] with i[1] < i[2] < ... < i[k] を満たす部分列を作れる最大の k を答える．

制約

• L <= 100000

解法

いわゆる最長増加部分列 (Longest Increasing Subsequence) 問題． 二分探索で O(L log L)．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int L;
 9   while (scanf("%d", &L) != EOF) {
10     vector<int> v;
11     for (int i = 0; i < L; i++) {
12       int x;
13       scanf("%d", &x);
14       const vector<int>::iterator it = lower_bound(v.begin(), v.end(), x);
15       if (it == v.end()) {
16         v.push_back(x);
17       } else {
18         *it = x;
19       }
20     }
21     printf("%lu\n", v.size());
22   }
23   return 0;
24 }