您现在的位置:首页 > >

HDU1423--Greatest Common Increasing Subsequence(LCIS)

发布时间:

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




1

5
1 4 2 5 -12
4
-12 1 2 4



?




Sample Output




2


#include
#include
#include
using namespace std;
#define maxn 580
int dp[maxn][maxn];
int len[maxn];
int key1[maxn],key2[maxn];
int LCIS(int n,int m)
{
memset(len,0,sizeof(len));
len[0] = 0;
for(int i = 1;i <= n;i++)
{
int locate = 0;
for(int j = 1;j <= m;j++)
{
if(key2[j] < key1[i] && len[locate] < len[j])
locate = j;
if(key2[j] == key1[i])
len[j] = len[locate] + 1;
}
}
int ans = -1;
for(int i = 1;i <= m;i++)
if(len[i] > ans)
ans = len[i];
return ans;
}

int main()
{
//freopen("in.txt","r",stdin);
int n,m,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d",&key1[i]);
scanf("%d",&m);
for(int i = 1;i <= m;i++)
scanf("%d",&key2[i]);
printf("%d
",LCIS(n,m));
if(t) printf("
");
}
return 0;
}




热文推荐
猜你喜欢
友情链接: