BNUOJ 4215 最长公共连续子序列
2024-09-02 05:31:43
最长公共连续子序列
Time Limit: 1000ms
Memory Limit: 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 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
int a[],b[],dp[][];
int main(){
int n,m,i,j,ans;
while(~scanf("%d %d",&n,&m)){
for(i = ; i <= n; i++)
scanf("%d",a+i);
for(j = ; j <= m; j++)
scanf("%d",b+j);
memset(dp,,sizeof(dp));
for(ans = ,i = ; i <= n; i++){
for(j = ; j <= m; j++){
if(a[i] == b[j]){
dp[i][j] = dp[i-][j-]+;
}
if(dp[i][j] > ans) ans = dp[i][j];
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- jQuery弹出提示信息简洁版(自动消失)
- [翻译]Apache Spark入门简介
- 【转】破解Source Insight 3.5.0072过程 附:安装软件+注册机
- 一个优秀的Android应用从建项目开始
- iframe 动态onload事件处理方式
- linux 中文件夹的文件按照时间倒序或者升序排列
- AndroidAnnotations部署
- Jenkins 十一: 构建Maven项目
- a 标签
- Insert into a Cyclic Sorted List
- Gimp教程:制作彩色的网站横幅
- hdu 1498
- 常用到的html页面布局和组件: 自己用
- Java基础学习笔记二十一 多线程
- 最新版-MySQL8.0 安装 - 改密码 之坑
- 一致性Hash漫画图解
- 帆软报表(finereport)使用row_number ()进行组内排序
- D. Vasya and Arrays
- Backbone.js 的 View 中定义事件
- 大家所说的full-stack框架到底是指什么?