POJ2533Longest Ordered Subsequence（DP）

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define MAX(a,b) (a > b ? a : b)
17 #define MIN(a,b) (a < b ? a : b)
18 #define mem0(a) memset(a,0,sizeof(a))
19 
20 typedef long long LL;
21 const double eps = 1e-12;
22 const int MAXN = 1005;
23 const int MAXM = 5005;
24 
25 int DP[1100], a[1100], N;
26 
27 int BinarySearch(int low, int high, int val)
28 {
29     while(low < high)
30     {
31         int mid = (low + high) >> 1;
32         if(DP[mid] < val) low = mid +1;
33         else high = mid;
34     }
35     return low;
36 }
37 
38 int main()
39 {
40     while(~scanf("%d", &N))
41     {
42         for(int i=1;i<=N;i++)
43         {
44             scanf("%d", &a[i]);
45         }
46         DP[1] = a[1];
47         int len = 1;
48         for(int i=2;i<=N;i++)
49         {
50             int id = BinarySearch(1, len+1, a[i]);
51             DP[id] = a[i];
52             if(id > len) ++len;
53         }
54         printf("%d
", len);
55     }
56     return 0;
57 }