题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1423
思路：dp[i][j]表示序列1(1-i)和序列2(1-j)最长的公共子序列
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=550; 7 int dp[MAXN][MAXN]; 8 int num1[MAXN]; 9 int num2[MAXN]; 10 int n1,n2; 11 //dp[i][j]表示num1[]从1-i,num2[]1-j的最长公共子序列 12 13 14 int main(){ 15 int _case,t=0; 16 scanf("%d",&_case); 17 while(_case--){ 18 memset(num1,0,sizeof(num1)); 19 memset(num2,0,sizeof(num2)); 20 if(t++)puts(""); 21 scanf("%d",&n1); 22 for(int i=1;i<=n1;i++)scanf("%d",&num1[i]); 23 scanf("%d",&n2); 24 for(int i=1;i<=n2;i++)scanf("%d",&num2[i]); 25 memset(dp,0,sizeof(dp)); 26 for(int i=1;i<=n1;i++){ 27 int ans=0; 28 for(int j=1;j<=n2;j++){ 29 dp[i][j]=dp[i-1][j]; 30 if(num2[j]<num1[i]&&ans<dp[i-1][j])ans=dp[i-1][j];//求出1-i,j中的最长公共子序列 31 if(num1[i]==num2[j]){ 32 dp[i][j]=ans+1; 33 } 34 } 35 } 36 int ans=0; 37 for(int i=1;i<=n2;i++)ans=max(ans,dp[n1][i]); 38 printf("%d\n",ans); 39 } 40 return 0; 41 } 42 43 44 45 46 47 48 49