最長公共連續(xù)子序列

Time Limit:?1000ms Memory Limit:?65536KB 64-bit integer IO format:?%lld????? Java class name:?Main

?給你兩個(gè)序列S1和S2，長度分別是L1，L2 (1 <= L1 , L2 <= 180).?

寫一個(gè)程序找出最長的連續(xù)公共子序列。 連續(xù)子序列定義為序列中連續(xù)的一個(gè)片段。例如序列"1 2 3"的子串有空串，"1"，"2"，"3"，"1 2"，"2 3"，"1 2 3"。

Input

第1行：兩個(gè)整數(shù)L1，L2，以一個(gè)空格隔開。

第2行到第L1+1行：每行一個(gè)整數(shù)，第i+1行給出S1中的第i個(gè)數(shù)。 第L1+2行到第L1+L2+1行：每行一個(gè)整數(shù)，第L1+i+1行給出S1中的第i個(gè)數(shù)。

Output

?一個(gè)整數(shù)，給出S1和S2的最長連續(xù)子序列的長度

Sample Input

10 12 1 1 1 3 2 3 3 3 4 5 1 1 1 1 3 2 3 3 4 4 5 -8

Sample Output

7

Source

第八屆北京師范大學(xué)程序設(shè)計(jì)競賽熱身賽第四場 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 long 10 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 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/crackpotisback/p/3835730.html

總結(jié)

以上是生活随笔為你收集整理的BNUOJ 4215 最长公共连续子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。