hdu 1423 最长公共递增子序列

时间：2021-07-07 23:58:37

这题一开始把我给坑了，我还没知道LCIS的算法，然后就慢慢搞吧，幸运的是还真写出来了，只不过麻烦了一点。

我是将该题转换为多条线段相交，然后找出最多多少条不相交，并且其数值死递增的。

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int dp[][];

int list1[],list2[];

struct Edge{

    int val,vex[];

    int pos;

}p[];

void init()

{

    int i,j;

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

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

            dp[i][j]=;

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

        p[i].pos=;

}

int main()

{

    int t,n,m,i,j,k,r,f;

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d",&n);

        for(i=;i<=n;i++)

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

        scanf("%d",&m);

        for(i=;i<=m;i++)

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

        int f=;

        for(i=;i<=n;i++)

        {

            for(j=;j<=m;j++)

            {

                if(list1[i]==list2[j])

                {

                    p[i].val=list1[i];

                    p[i].vex[p[i].pos++]=j;

                    f=;

                }

            }

        }

        /*for(i=1;i<=n;i++)

        {

            cout<<" ** "<<p[i].val<<" ** :";

            for(j=0;j<p[i].pos;j++)

                cout<<p[i].vex[j]<<" ";

            cout<<endl;

        }*/

        int Max=;

        if(f)

            Max=;

        for(i=;i<=n;i++)

        {

            for(j=;j<i;j++)

            {

                if(p[i].val>p[j].val)

                {

                    //cout<<"ok"<<endl;

                    //cout<<p[i].val<<"   "<<p[j].val<<endl;

                    for(k=;k<p[i].pos;k++)

                    {

                        for(r=;r<p[j].pos;r++)

                        {

                            if(p[i].vex[k]>p[j].vex[r])

                                dp[i][p[i].vex[k]]=max(dp[i][p[i].vex[k]],dp[j][p[j].vex[r]]+);

                            if(dp[i][p[i].vex[k]]>Max)

                            {

                                Max=dp[i][p[i].vex[k]];

                                //cout<<Max<<endl;

                            }

                        }

                    }

                }

            }

        }

        printf("%d\n",Max);

        if(t)

            printf("\n");

    }

    return ;

}

正解的代码有如下两种版本，一种是一维数组，一种二维。思想是一样的。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int dp[][],a[],b[];

int LCIS(int n,int m)

{

    int i,j,k,temp;

    int ans=;

    memset(dp,,sizeof(dp));

    for(i=;i<=n;i++)

    {

        temp=;

        for(j=;j<=m;j++)

        {

            dp[i][j]=dp[i-][j];

            if(a[i]==b[j]) dp[i][j]=temp+;

            if(a[i]>b[j]&&dp[i-][j]>temp)

                temp=dp[i-][j];

            if(ans<dp[i][j])

                ans=dp[i][j];

        }

    }

    return ans;

}

int main()

{

    int t,n,m,i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(i=;i<=n;i++)

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

        scanf("%d",&m);

        for(i=;i<=m;i++)

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

        printf("%d\n",LCIS(n,m));

        if(t)

            printf("\n");

    }

}
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int f[],a[],b[];

int LCIS(int n,int m)

{

    int i,j,k;

    memset(f,,sizeof(f));

    for(i=;i<=n;i++)

    {

        k=;

        for(j=;j<=m;j++)

        {

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

                f[j]=max(f[j],k+);

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

                k=f[j];

            //cout<<k<<endl;

        }

    }

    int ans=;

    for(i=;i<=m;i++)

        ans=max(ans,f[i]);

    return ans;

}

int main()

{

    int t,n,m,i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(i=;i<=n;i++)

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

        scanf("%d",&m);

        for(i=;i<=m;i++)

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

        printf("%d\n",LCIS(n,m));

        if(t)

            printf("\n");

    }

}

相关文章