CC

自然万物都趋向从有序变得无序

0%

POJ 2533 Longest Ordered Subsequence

发表于 更新于 分类于 Valine：

Longest Ordered Subsequence

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence ( a1, a2, ..., aN) be any sequence ( ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). 

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

题意

最长上升子序列问题,

思路

1 复杂度 O(n*n) dp[i]表示前i个数所能构成的最长上升子序列的长度,每一个的dp[i]都是前i-1个数构成的最大长度+1,所以每次遍历前i-1个数,找到最大的情况.最后遍历所有情况找到最大的解即可.
2 复杂度 O(n*logn) 开一个数组来来存这个最长上升子序列,如果最新的数比dp[k]大,则我们让这个新数存到数组dp[k]的下一位,并且更新数组长度,如果当前数a[i]比数组的最大的数(即dp数组的最后一个数)小,那么我们查找数组dp中刚刚好大于等于a[i]的这个数并进行替换,查找的过程我们用二分查找,所以时间复杂度大大的降低了.
以样例为例子:
dp[1]=1;
a[2]=7比dp[1]大,则dp[2]=7;
a[3]=3比dp[2]小,则二分查找,然后替换dp[2],则dp[2]=3;
a[4]=5比dp[2]大,则dp[3]=5;
a[5]=9比dp[3]大,则dp[4]=9;
a[6]=4比dp[4]小,则查找替换,dp[3]=4;
a[7]=8比dp[4]小,则查找替换,dp[4]=8,
所有最长上升子序列的长度为4.

代码

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int dp[10000+10];
int a[10000+10];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
            memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i)
        {
            int l=0,k=0;
            for(int j=1;j<i;++j)//遍历寻找最大的长度
                if(a[i]>a[j]&&dp[j]>k)
            {
                k=dp[j];
                l=j;
            }
            dp[i]=dp[l]+1;//在最大的长度前+1,如果没有则是w[0]+1=0+1,好像也没毛病
        }
        int ans=0;
        for(int i=1;i<=n;++i)
            ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int dp[10000+10];
int a[10000+10];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
            memset(dp,0,sizeof(dp));
        int k=1;
        dp[k]=a[1];
        for(int i=2;i<=n;++i)
        {
           if(a[i]>dp[k])
            dp[++k]=a[i];
           else {
            int cnt=lower_bound(w+1,w+1+k,a[i])-w;
            dp[cnt]=a[i];
           }
        }
        printf("%d\n",k);
    }
    return 0;
}