程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1423 Greatest Common Increasing Subsequence

hdu 1423 Greatest Common Increasing Subsequence

編輯:C++入門知識

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;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved