[动规]这个的东西zhen有趣LCS(最长公共子序列)

啊哈磊

样例输入：
5
5 6 4 3 9
6
6 3 9 5 6 9

样例输出：
3

代码：

1. 
   
2. // Author: Ahalei
   
3. // Date: 11 1, 2010
   
4. // City: Wuhan
   
5. // Website: www.ahalei.com
   
6. // Title: LCS (Longest Common Subsequence)
   
7. #include <cstdio>
   
8. 
   
9. int max(int x,int y)
   
10. {
    
11.     return x>y?x:y;//三目运算符，返回x和y中较大的一个，如过这个不知道，百度一下
    
12. }
    
13. 
    
14. int main()
    
15. {
    
16.     int f[11][11]={0};
    
17.     int a[11],b[11];
    
18.     int n,m,i,j;
    
19.    
    
20.    
    
21.     scanf("%d",&n);//读取第1个序列的长度
    
22.     for(i=1;i<=n;i++)//读取第1个序列
    
23.         scanf("%d",&a);
    
24.     scanf("%d",&m);//读取第2个序列的长度
    
25.     for(i=1;i<=m;i++)//读取第2个序列
    
26.         scanf("%d",&b);
    
27.    
    
28.     //将序列a中的每个元素和序列b中的每个元素相比较
    
29.     for(i=1;i<=n;i++)
    
30.         for(j=1;j<=m;j++)
    
31.         {
    
32.             if(a[i]==b[j])//如果他们相等
    
33.             {
    
34.                 f[i][j]=f[i-1][j-1]+1;//就是他左上角的值(上一次他们相等的时候)+1
    
35.             }
    
36.             else//如果他们不相等
    
37.             {
    
38.                 f[i][j]=max(f[i-1][j],f[i][j]);
    
39.                 f[i][j]=max(f[i][j-1],f[i][j]);
    
40.             }
    
41.         }
    
42.     //f[n][m]就是他们的最长公共子序列的个数
    
43.     printf("%d\n",f[n][m]);
    
44.     return 0;
    
45. }
    
46. 
    

复制代码