LCIS最长公共上升子序列！HDU-1423-白红宇

LCIS最长公共上升子序列！HDU-1423

阅读量：7039 次

发布时间：2019-06-28

本文共 1731 字，大约阅读时间需要 5 分钟。

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

InputEach sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.Outputoutput print L - the length of the greatest common increasing subsequence of both sequences.Sample Input
151 4 2 5 -124-12 1 2 4
Sample Output
2

　　还是套路，套路代码：

设题目给出a[],b[]两个序列。f[j]表示b序列到j的时候，与a[？？]序列构成最长公共上升子序列的最优解。其中a[？？]序列，从1到n枚举过来。

　　如果某一个时刻a[i]==b[j]，那么显然，我们就应该在0到j-1中，找一个f值最大的来更新最优解。这和求上升子序列是思想是一样的。另外，在枚举b[j]的时候，我们顺便保存一下小于a[i]的f值最大的b[j]，这样在更新的时候，我们就可以做到O(1)的复杂度，从而将整个算法的复杂度保证在O(nm)

分析来源：http://www.cnblogs.com/ka200812/archive/2012/10/15/2723870.html

详细分析：http://blog.csdn.net/wall_f/article/details/8279733

1 for(int i=1;i<=n;i++) 2         { 3             mx=0; 4             for(int j=1;j<=m;j++) 5             { 6                 dp[i][j]=dp[i-1][j]; 7                 if(a[i]>b[j]&&mx

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
           6 using namespace std; 7 int dp[600][600]; 8 int a[600],b[600]; 9 int main()10 {11     int T;12     cin>>T;13     while(T--)14     {15         int n,m;16         scanf("%d",&n);17         for(int i=1;i<=n;i++)18             scanf("%d",&a[i]);19         scanf("%d",&m);20         for(int i=1;i<=m;i++)21             scanf("%d",&b[i]);22         memset(dp,0,sizeof(dp));23         int mx;24         for(int i=1;i<=n;i++)25         {26             mx=0;27             for(int j=1;j<=m;j++)28             {29                 dp[i][j]=dp[i-1][j];30                 if(a[i]>b[j]&&mx

转载于:https://www.cnblogs.com/ISGuXing/p/7248119.html

你可能感兴趣的文章