poj 3903 最长上升子序列 Stock Exchange

bestjoe

　　题目链接：http://poj.org/problem?id=3903





1 #include <cstdio>
2 #include <cmath>
3 #include <algorithm>
4 #include <iostream>
5 #include <cstring>
6 #include <queue>
7 #include <vector>
8 #define maxn 100005
9 using namespace std;
10
11 int stack[maxn];
12 int a[maxn];
13 int n;
14
15 int search_lower_bound(int l,int h,int m){
16     if(l == h) return h;
17     int mid = (l + h)/2; //printf("%d\n",mid);
18     if(stack[mid] < m)   return search_lower_bound(mid+1,h,m);
19     else                 return search_lower_bound(l,mid,m);
20 }
21
22 int main()
23 {
24     if(freopen("input.txt","r",stdin)== NULL)  {printf("Error\n"); exit(0);}
25
26     while(cin>>n){
27         for(int i=0;i<n;i++) scanf("%d",&a);
28         int rear = 0;
29         stack[0] = a[0];
30         for(int i=1;i<n;i++){
31             if(a>stack[rear]){
32                 rear++;
33                 stack[rear] = a;
34             }
35             else{
36                 int temp = search_lower_bound(0,rear,a);
37                 //printf("%d %d %d\n",temp,stack[temp],a);
38                 stack[temp] = a;
39             }
40         }
41         printf("%d\n",rear+1);
42     }
43 }
View Code