首页 > 代码库 > BNUOJ 4215 最长公共连续子序列
BNUOJ 4215 最长公共连续子序列
最长公共连续子序列
1000ms
65536KB
64-bit integer IO format: %lld Java class name: Main
给你两个序列S1和S2，长度分别是L1，L2 (1 <= L1 , L2 <= 180).
写一个程序找出最长的连续公共子序列。
连续子序列定义为序列中连续的一个片段。例如序列"1 2 3"的子串有空串，"1"，"2"，"3"，"1 2"，"2 3"，"1 2 3"。
Input
第1行：两个整数L1，L2，以一个空格隔开。
第2行到第L1+1行：每行一个整数，第i+1行给出S1中的第i个数。
第L1+2行到第L1+L2+1行：每行一个整数，第L1+i+1行给出S1中的第i个数。
Output
一个整数，给出S1和S2的最长连续子序列的长度
Sample Input
10 12111323334511113233445-8
Sample Output
7
Source
第八届北京师范大学程序设计竞赛热身赛第四场
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 int a[200],b[200],dp[200][200];12 int main(){13 int n,m,i,j,ans;14 while(~scanf("%d %d",&n,&m)){15 for(i = 1; i <= n; i++)16 scanf("%d",a+i);17 for(j = 1; j <= m; j++)18 scanf("%d",b+j);19 memset(dp,0,sizeof(dp));20 for(ans = 0,i = 1; i <= n; i++){21 for(j = 1; j <= m; j++){22 if(a[i] == b[j]){23 dp[i][j] = dp[i-1][j-1]+1;24 }25 if(dp[i][j] > ans) ans = dp[i][j];26 }27 }28 printf("%d\n",ans);29 }30 return 0;31 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。