HOJ 2985 Wavio Sequence(最長インクリメントサブシーケンスおよびそのO(n＊logn)アルゴリズム)

Wavio Sequence My Tags(Edit)Source:UVA Time limit:1 sec Memorylimit:32 M Submitted:296,Acctepted:123 Wavio is a sequence of integers.It has some interestititititities.Wavio is is properties.Wavio isisis propertities.Waviis.Wavis.Waviisisisisisisisisisisis propertities.Wavidededededededededededededededededededededededededededededededededededededededededededededededededeties.Wavi. The last(n＋1)integers of Wavio sequence makes a strictly decreasung sequence.No two adjacent integers are same in a Wavio sequence.For example 1,2,4,4,4,3,2,0 is Wavio sequence of length 9.But 3,prores 2,5You will be given a sequence of integers.You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence.Consder,the given sequence as:1 3 3 3.Heven 2the output will be 9.Input The input file contains multile test cases.The description of each test case is given below.Input is terminated by of file.Each set starts with a postive integer,N(1≦)10000In next fewラインthere will be N integers.Output For each set of input print the length of longest wavio sequence in a line.Sample Input 10 1 2 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 O 2 2 2 2 3 3 3 3 put 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 mp 3 3 3 3 3 3 3 3 3 3 3 3 3 mp 5 e 1
解法は、配列を正と逆にして、それぞれの最長の増分サブシーケンスを求めて、iを遍歴しています.i左の配列と右の配列の最長男シーケンスが等しいなら、条件に合致します.最長インクリメントサブシーケンスを求める場合はO(N^2)でタイムアウトしますので、効率の高いアルゴリズムを使用しなければなりません.Oアルゴリズムについては以下のブログを参照してください.http://blog.csdn.net/dacc123/article/details/50571844 コードを付ける

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;
int a[10005];
int b[10005];
int c[10005];
int d[10005];
int dp[10005];
int bp[10005];
int n;
int ans;
int search(int num,int l,int r,int *dp)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(num>dp[mid])
            l=mid+1;
        else
            r=mid-1;
    }
    return l;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[n-i+1]=a[i];
        }
        //memset(dp,0,sizeof(dp));
        dp[1]=a[1];
        c[1]=1;
        int len=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>dp[len])
                dp[++len]=a[i];
            else
            {
                int pos=search(a[i],1,len,dp);
                dp[pos]=a[i];
            }
            c[i]=len;
        }
        bp[1]=b[1];
        d[1]=1;
        int len2=1;
        for(int i=2;i<=n;i++)
        {
            if(b[i]>bp[len2])
                bp[++len2]=b[i];
            else
            {
                int pos=search(b[i],1,len2,bp);
                bp[pos]=b[i];
            }
            d[i]=len2;
        }
        for(int i=1;i<=n;i++)
        {
            if(c[i]==d[n-i+1])
                ans=max(ans,c[i]*2-1);
        }
        printf("%d
",ans);

    }
    return 0;
}