EOJ 2743 Stock Exchange

hb120973135

　　EOJ 2743  http://acm.cs.ecnu.edu.cn/problem.php?problemid=2743
　　本题为LIS：即Longest Increasing Sequence.（本题中严格递增）
　　最长上升子序列(LIS)长度的O(nlogn)算法：(对状态转移时查找的优化)
　　用len[ i ]存放当前（需不断更新） 长度为 i 的上升子序列的末尾 的最小值，
　　注意到，len[]严格递增，可对其进行二分查找，
　　找到最大的 i ,且满足len[ i ] < x 即可;
　　





1 #include <iostream>
2 #include <stdio.h>
3 #include <string>
4 #include <algorithm>
5 #include <string.h>
6 #include <stdlib.h>
7
8 using namespace std;
9  
10 int num[100005];
11 int dp[100005];
12 int len[100005];
13 int n;
14  
15 int search(int x)
16 {
17     int l = 1, r = n, m;
18     while(l <= r)
19     {
20         m = (l + r)/2;
21         if(x > len[m])
22                l = m+1;      // l的左边(i<l)始终满足len <  x;
23         else
24             r = m-1;      // r的右边(j>r)始终满足len[j] >= x;
25     }
26     return l-1;
27 }
28  
29 int main()
30 {
31     while(scanf("%d", &n) != EOF)
32     {            
33         for(int i=1; i<=n; i++)
34             scanf("%d", &num);            
35               
36         memset(len, 0x3f, sizeof(len));              
37         for(int i=1; i<=n; i++)
38         {
39             dp = search(num) + 1;                  
40             len[dp] = min(len[dp], num);                        
41         }
42                             
43         int ans = 0;
44         for(int i=1; i<=n; i++)
45             ans = max(ans, dp);
46         printf("%d\n", ans);
47     }
48     return 0;
49 }
View Code