Problem Description

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

 

Input

Each
sequence is described with M - its length (1 <= M <= 500) and M
integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.

 

Output

output print L - the length of the greatest common increasing subsequence of both sequences.

 

Sample Input

 

Sample Output

 

Source

ACM暑期集训队练习赛（二）

 

Recommend

lcy   |   We have carefully selected several similar problems for you:  1422 1400 1418 1424 1401 

#include<algorithm>

#include<string>

#include<string.h>

#include<stdio.h>

#include<iostream>

using namespace std;

#define N 505

int a[N],l1,l2,b[N],ma,f[N][N],d[N];

void solve1()//O(n^4)

{

    ma = ;

    memset(f, , sizeof(f) );

    for(int i = ; i <= l1; i++)

        for(int j = ; j <= l2; j++)

        {

            if(a[i-] == b[j-])

            {

                int ma1 = ;

                for(int i1 = ; i1 < i; i1++)

                    for(int j1 = ; j1 < j; j1++)

                        if(a[i1-] == b[j1-]  &&  a[i1-] < a[i-]  &&  f[i1][j1] > ma1)//实际上a[i-1]==b[j1-1]可以省，因为既然f[i1][j1]+1>f[i][j]了，

                            ma1 = f[i1][j1];                                             /*说明肯定a[i-1]==b[j1-1]了，因为这种解法只有当a[i-1]==b[j-1]时，f[i][j]才不等于0*/

                f[i][j] = ma1 + ;

            }

            ma = max(ma, f[i][j]);

        }

    cout<<ma<<endl;

}

void solve2()//O(n^3)

{

    ma = ;

    memset(f, , sizeof(f) );

    for(int i = ; i <= l1; i++)

        for(int j = ; j <= l2; j++)

        {

            f[i][j] = f[i-][j];

            if(a[i-] == b[j-])

            {

                int ma1 = ;

                for(int j1 = ; j1 < j; j1++)

                {

                    if(b[j1-] < b[j-]  &&  f[i-][j1] > ma1)

                        ma1 = f[i-][j1];

                }

                f[i][j] = ma1 + ;

        }

        ma = max(ma, f[i][j]);

    }

    cout<<ma<<endl;

}

void solve3()//O(n^2)

{

    memset(f, , sizeof(f) );

    for(int i = ; i <= l1; i++)

    {

        int  ma1 = ;

        for(int j = ; j <= l2; j++)

        {

            f[i][j] = f[i-][j];//带这种的一般都能压缩一维空间，也就是简化空间复杂度

            if(a[i-] > b[j-]  &&  f[i-][j] > ma1)

                ma1 = f[i-][j];

            if(a[i-] == b[j-])

                f[i][j] = ma1 + ;

        }

    }

    ma = -;

    for(int j = ;j <= l2; j++)

        ma=max(ma,f[l1][j]);

    cout<<ma<<endl;

}

void solve4()//O(n^2)//优化空间复杂度

{

    ma = ;

    memset(d, , sizeof(d) );

    for(int i = ; i <= l1; i++)

    {

        int ma1 = ;

        for(int j = ; j <= l2; j++)

        {

            if(a[i-] > b[j-]  &&  d[j] > ma1)

                ma1 = d[j];

            if(a[i-] == b[j-])

                d[j] = ma1 + ;

        }

    }

    ma = -;

    for(int j = ;j <= l2; j++)

        ma = max(ma, d[j]);

    cout<<ma<<endl;

}

int main()

{

    int T;cin>>T;

    while(T--)

    {

        scanf("%d", &l1);

        for(int i = ; i < l1; i++)

            scanf("%d", &a[i]);

        scanf("%d", &l2);

        for(int i = ; i < l2; i++)

            scanf("%d", &b[i]);

//        solve1();

//        solve2();

//        solve3();

        solve4();

        if(T)

            printf("\n");

    }

    return ;

}

/*

99

5

1 4 2 5 -12

4

-12 1 2 4

9

3 5 1 6 7 9 1 5 13

6

4 6 13 9 13 5

*/