uva10635(最长上升子列)

青旅半醒 2021-12-22 06:39 169阅读 0赞

题意：给出两个数列，每个数列的数都不同，求两个数列的最长公共子列(LCS)，输出长度。

分析：LCS转化为LIS。因为两个数组中每个数都不同，所以先将A数组按顺序对应1,2,3,4...p+1,

再把B数组与A数组共有的数用1,2,3...p+1替换，仅B数组中有的数则舍去，形成一个新序列 C ，

再求C的最长上升序列(LIS)。

复杂度n\*n代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>//最长上升子列 
    using namespace std;
    int A[1000000],B[1000000],dp[1000000];
    int main()
    {
        int T,cas=0,n,N,M;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&n,&N,&M);
            memset(A,0,sizeof(A));
            int x;
            for(int i=1;i<=N+1;i++)
            {
                scanf("%d",&x);
                A[x]=i;
            }
            int len=0;
            for(int i=1;i<=M+1;i++)
            {
                scanf("%d",&x);
                if(A[x]) B[len++]=A[x];
            }
            //求数组B的LIS,最长上升子列 
    /*考虑B[i]的决策,B[i]要么为前i个数中某个LIS的结尾,要么是开头第一个数 
    dp[i]为以B[i]为结尾的LIS 
    j:0->i-1 if(B[i]>B[j]) dp[i]=dp[j]+1;else dp[i]=1;
    */        
            memset(dp,0,sizeof(dp));
            dp[0]=1;
            int ans=0;
            /*for(int i=1;i<len;i++)超时 
            {
                for(int j=0;j<i;j++)
                if(B[i]>B[j]&&dp[j]>dp[i]) dp[i]=dp[j];
                dp[i]++;
                ans=max(ans,dp[i]);
            }*/
            for(int i=1;i<len;i++) 
            {
                dp[i]=1;
                for(int j=0;j<i;j++)
                if(B[i]>B[j]) dp[i]=max(dp[j]+1,dp[i]);
                ans=max(ans,dp[i]);
            }
            printf("Case %d: %d\n",++cas,ans);
        }
        return 0;
    }

复杂度nlogn

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>//最长上升子列 
    #define INF 999999999
    using namespace std;
    int A[90000],B[90000],dp[90000];
    int main()
    {
        int T,cas=0,n,N,M;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&n,&N,&M);
            memset(A,0,sizeof(A));
            int x;
            for(int i=1;i<=N+1;i++)
            {
                scanf("%d",&x);
                A[x]=i;
            }
            int len=0;
            for(int i=1;i<=M+1;i++)
            {
                scanf("%d",&x);
                if(A[x]) {dp[len]=INF;B[len++]=A[x];}
            }
    /*dp[i]表示长度为i+1的上升子列末尾元素的最小值,则dp[i]必递增,所以可以用二分法,初始化dp[i]=INF*/
            for(int i=0;i<len;i++)
                *lower_bound(dp,dp+len,B[i])=B[i];//找到不大于B[i]的第一个元素,替换成B[i] 
            printf("Case %d: %d\n",++cas,lower_bound(dp,dp+len,INF)-dp);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ACRykl/p/8296152.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/0444014c2d814c188ce280f3006f6088.png