2013
12-10

# Greatest Common Increasing Subsequence

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

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 print L – the length of the greatest common increasing subsequence of both sequences.

1

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

2

#include<stdio.h>
#include<string.h>
#define N 505
int main()
{
int n,m;
int a[N],b[N],f[N];
int i,j,k;
int ans;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&m);
for(i=1;i<=m;i++)
scanf("%d",&a[i]);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
memset(f,0,sizeof(f));
for(i=1;i<=m;i++)
{
k=0;
for(j=1;j<=n;j++)
{
if(b[j]<a[i]&&f[j]>f[k])
k=j;
if(b[j]==a[i])
f[j]=f[k]+1;
}
}
ans=0;
for(i=0;i<=n;i++)
{
if(ans<f[i])
ans=f[i];
}
printf("%d\n",ans);
if(T!=0)
printf("\n");
}
return 0;
}

1. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

2. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）