EOJ 2743 Stock Exchange
EOJ 2743http://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;
11 int dp;
12 int len;
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)
22 l = m+1; // l的左边(i<l)始终满足len <x;
23 else
24 r = m-1; // r的右边(j>r)始终满足len >= 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] = min(len], 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
页:
[1]