Poj3903 Stock Exchange

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 227 | 阅读时长 ≈ 1

Description

The world financial crisis is quite a subject. Some people are more relaxed while others are quite anxious. John is one of them. He is very concerned about the evolution of the stock exchange. He follows stock prices every day looking for rising trends. Given a sequence of numbers p1, p2,…,pn representing stock prices, a rising trend is a subsequence pi1 < pi2 < … < pik, with i1 < i2 < … < ik. John’s problem is to find very quickly the longest rising trend.

Input

Each data set in the file stands for a particular set of stock prices. A data set starts with the length L (L ≤ 100000) of the sequence of numbers, followed by the numbers (a number fits a long integer). White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

Output

The program prints the length of the longest rising trend. For each set of data the program prints the result to the standard output from the beginning of a line.

Sample Input

1
2
3
4
5
6
6 
5 2 1 4 5 3 
3  
1 1 1 
4 
4 3 2 1

Sample Output

1
2
3
3 
1 
1

Analysis

有一个长为n的数列a0,a1,…,an-1.求出最长上升子序列的长度，即对于任意的ii</sub>j</sub>的最长的子序列。

如果子序列的长度相同，那么最末位的元素较小的在之后会更加有优势，所以用DP针对相同长度情况下最小的末位元素进行求解。

​ dp[i]=长度为i+1的上升子序列中末位元素的最小值(不存在的话就是INF).

最开始全部dp[i]的值都为INF，由前到后逐个考虑数列的元素，对于每个aj，如果i=0或者dp[i-1]j</sub>的话，就用dp[i]=min(dp[i],aj)进行更新。

此方法复杂度为O(n2)，可以利用STL中的lower_bound函数进行二分优化，该函数从以排好序的序列a中利用二分搜索找出指向满足ai>=k的ai的最小的指针。优化后复杂度为O(nlogn)。

例如输入样例为n=5,a={4,2,3,1,5}:

i 0 1 2 3 4
dp[i] ∞ ∞ ∞ ∞ ∞
插入4
i 0 1 2 3 4
dp[i] 4 ∞ ∞ ∞ ∞
插入2
i 0 1 2 3 4
dp[i] 2 ∞ ∞ ∞ ∞
插入3
i 0 1 2 3 4
dp[i] 2 3 ∞ ∞ ∞
插入1
i 0 1 2 3 4
dp[i] 1 3 ∞ ∞ ∞
插入5
i 0 1 2 3 4
dp[i] 1 3 5 ∞ ∞

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm>
#include <cstring>
using namespace std;
int a[100000 + 5], dp[100000 + 5];
const int INF = 1000000;
int main()
{
	int t,i;
	while(scanf("%d",&t)!=EOF)
	{
		memset(dp, INF, sizeof(dp));
		for(i = 0; i < t; i++)
		{
			scanf("%d", &a[i]);
		}
		for(i = 0; i < t; i++)
		{
			*lower_bound(dp, dp + t, a[i]) = a[i];
		}
		printf("%d\n", lower_bound(dp, dp + t, INF) - dp);
	}
	return 0;
}