poj 3903 最长上升子序列 Stock Exchange
题目链接：http://poj.org/problem?id=39031 #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;
12 int a;
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 < 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 = a;
30 for(int i=1;i<n;i++){
31 if(a>stack){
32 rear++;
33 stack = a;
34 }
35 else{
36 int temp = search_lower_bound(0,rear,a);
37 //printf("%d %d %d\n",temp,stack,a);
38 stack = a;
39 }
40 }
41 printf("%d\n",rear+1);
42 }
43 }
View Code
页:
[1]