hdu1423---Greatest Common Increasing Subsequence(最长公共上升子序列)-白红宇的个人博客

hdu1423---Greatest Common Increasing Subsequence(最长公共上升子序列)

发布日期：2022-02-02 02:58:12 浏览次数：4 分类：技术文章

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

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

151 4 2 5 -124-12 1 2 4

Sample Output

2代码实现：   
   #include 
    
     #include 
     
      using namespace std;int a[501],b[501];int dp[501][501];int main(){
      
int t,len1,len2,max;
      
cin>>t;
      
while(t--)
      
{
      
memset(dp,0,sizeof(dp));
      
cin>>len1;
      
for(int i=1; i<=len1; i++)
      
{
      
cin>>a[i];
      
}
      
cin>>len2;
      
for(int j=1; j<=len2; j++)
      
{
      
cin>>b[j];
      
}
      
for(int i=1; i<=len1; i++)
      
{
      
max=0;
      
for(int j=1; j<=len2; j++)
      
{
      
dp[i][j]=dp[i-1][j];
      
if(a[i]>b[j]&&max
      
       
{
       
max=dp[i-1][j];
       
}
       
if(a[i]==b[j])
       
{
       
dp[i][j]=max+1;
       
}
       
}
       
}
       
max=0;
       
for(int j=1; j<=len2; j++)
       
{
       
if(max
       
        
{
        
max=dp[len1][j];
        
}
        
}
        
cout<
        
         <
         
          
if(t)
          
{
          
cout<
          
           
}
           
}
           
return 0;}

转载地址：https://blog.csdn.net/u010368749/article/details/20448943 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：hdu1080---Human Gene Functions

下一篇：最长公共上升子序列（LIS）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

最新文章