ZOJ 1986 Bridging Signals

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=986

最长上升子序列……

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAXN = 40000 + 10;
 5 
 6 int n;
 7 int num[MAXN];
 8 int stack[MAXN];
 9 
10 int Bsearch( int x, int y, int v )
11 {
12     int m;
13     while ( x < y )
14     {
15         m = x + (y - x) / 2;
16         if ( stack[m] == v ) return m;
17         else if ( stack[m] > v ) y = m;
18         else x = m + 1;
19     }
20     return m;
21 }
22 
23 int DP()
24 {
25     int top = 0;
26 
27     stack[ ++top ] = num[0];
28 
29     for ( int i = 1; i < n; i++ )
30     {
31         if ( num[i] > stack[top] ) stack[ ++top ] = num[i];
32         else
33         {
34             int temp = Bsearch( 1, top + 1, num[i] );
35             if (stack[temp] > num[i])
36                 stack[temp] = num[i];
37             else stack[temp + 1] = num[i];
38         }
39     }
40 
41     return top;
42 }
43 
44 int main()
45 {
46     int T;
47     scanf("%d", &T);
48     while ( T-- )
49     {
50         scanf( "%d", &n );
51         for ( int i = 0; i < n; i++ )
52             scanf( "%d", &num[i] );
53 
54         printf( "%d\n", DP() );
55     }
56     return 0;
57 }