hdu1423Greatest Common Increasing Subsequence（最长公共递增子序列）

超、凢脫俗 2022-08-22 00:21 189阅读 0赞

# Greatest Common Increasing Subsequence #

##### Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other) #####

##### Total Submission(s) : 10   Accepted Submission(s) : 3 #####

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

1
    
    5
    1 4 2 5 -12
    4
    -12 1 2 4

Sample Output

Source

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

题意：

求两个数组的最长公共递增子序列

\#include<cstdio>  
\#include<cstring>  
int a\[10000\],b\[10000\],dp\[1000\]\[1000\];  
int main()  
\{  
    int n;  
    scanf("%d",&n);  
    while(n--)  
    \{  
        int x1,x2,i,j,max1;  
        scanf("%d",&x1);  
        for(i=0;i<x1;i++)  
        scanf("%d",&a\[i\]);  
        scanf("%d",&x2);  
        for(i=0;i<x2;i++)  
        scanf("%d",&b\[i\]);  
        memset(dp,0,sizeof(dp));  
        for(i=1;i<=x1;i++)  
        \{  
            max1=0;  
            for(j=1;j<=x2;j++)  
            \{  
                dp\[i\]\[j\]=dp\[i-1\]\[j\];//至少等于前面的  
                if(a\[i-1\]>b\[j-1\]&&max1<dp\[i-1\]\[j\])//有可能在公共子序列里面；  
                    max1=dp\[i-1\]\[j\];  
                if(a\[i-1\]==b\[j-1\])//相等就说明是递增子序列里面的。  
                    dp\[i\]\[j\]=max1+1;  
            \}  
        \}  
        max1=0;  
        for(i=0;i<=x1;i++)//找出较大的  
            for(j=0;j<=x2;j++)  
            if(max1<dp\[i\]\[j\])  
            max1=dp\[i\]\[j\];  
        printf("%d\\n",max1);  
        if(n)printf("\\n");//注意就是最后的没有换行。  
    \}  
  
  
\}