Greatest Common Increasing Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2847 Accepted Submission(s): 885
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<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 510 #define inf 0x3fffffff int a[N],b[N]; struct node{ int l,k; }f[N]; void up(node &x,node &y){ if(x.l==y.l&&x.k>y.k)x.k=y.k; if(x.l<y.l){x.l=y.l;x.k=y.k;} } int main(){ int i,j,k; int T,n,m; scanf("%d",&T); while(T--){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); scanf("%d",&m); for(i=1;i<=m;i++)scanf("%d",&b[i]); for(j=1;j<=m;j++){f[j].l=0;f[j].k=inf;} f[0].l=0;f[0].k=-inf; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ up(f[j],f[j-1]); if(a[i]==b[j]&&a[i]>f[j-1].k){ node t; t.l=f[j-1].l+1; t.k=a[i]; up(f[j],t); } } } //for(i=0;i<=m;i++)printf("%d %d\n",f[i].l,f[i].k); printf("%d\n",f[m].l); if(T)printf("\n"); } return 0; }