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)

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.249.68.14]2022年05月23日 04时20分59秒