hdu1950 Bridging signals 最长递增子序列

　　用一个数组记下递增子序列长度为i时最小的len[i],不断更新len数组,最大的i即为最长递增子序列的长度

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define MAX 40010
 4 using namespace std;
 5 int a, T, n, len[MAX];
 6 int* lower(int &val, int R) //二分找值，返回下标
 7 {
 8     int L = 0, mid;
 9     while (L < R)
10     {
11         mid = R - (R - L + 1) / 2;            //保证至少减少1
12         if (len[mid] < val)    L = mid + 1;//至少增加1
13         else                R = mid;
14     }
15     return &len[R];
16 }
17 int main()
18 {
19     scanf("%d", &T);
20     while (T--)
21     {
22         scanf("%d", &n);
23         int i, l = 0;
24         scanf("%d", &a);
25         len[0] = a;
26         for (i = 1; i < n; i++)
27         {
28             scanf("%d", &a);
29             if (a>=len[l]) len[++l] = a;
30             else *lower(a, l) = a;
31             //            else *upper_bound(len,len+l+1,a) = a;
32         }
33         printf("%d
", l + 1);
34     }
35     return 0;
36 }

View Code