样例输入:
5
5 6 4 3 9
6
6 3 9 5 6 9 样例输出:
3
代码:
- // Author: Ahalei
- // Date: 11 1, 2010
- // City: Wuhan
- // Website: www.ahalei.com
- // Title: LCS (Longest Common Subsequence)
- #include <cstdio>
- int max(int x,int y)
- {
- return x>y?x:y;//三目运算符,返回x和y中较大的一个,如过这个不知道,百度一下
- }
- int main()
- {
- int f[11][11]={0};
- int a[11],b[11];
- int n,m,i,j;
-
-
- scanf("%d",&n);//读取第1个序列的长度
- for(i=1;i<=n;i++)//读取第1个序列
- scanf("%d",&a);
- scanf("%d",&m);//读取第2个序列的长度
- for(i=1;i<=m;i++)//读取第2个序列
- scanf("%d",&b);
-
- //将序列a中的每个元素和序列b中的每个元素相比较
- for(i=1;i<=n;i++)
- for(j=1;j<=m;j++)
- {
- if(a[i]==b[j])//如果他们相等
- {
- f[i][j]=f[i-1][j-1]+1;//就是他左上角的值(上一次他们相等的时候)+1
- }
- else//如果他们不相等
- {
- f[i][j]=max(f[i-1][j],f[i][j]);
- f[i][j]=max(f[i][j-1],f[i][j]);
- }
- }
- //f[n][m]就是他们的最长公共子序列的个数
- printf("%d\n",f[n][m]);
- return 0;
- }
复制代码
|