首页 > 代码库 > nyoj 760
nyoj 760
ee LCS again
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
There are A, B two sequences, the number of elements in the sequence is n、m;
Each element in the sequence are different and less than 100000.
Calculate the length of the longest common subsequence of A and B.
- 输入
- The input has multicases.Each test case consists of three lines;
The first line consist two integers n, m (1 < = n, m < = 100000);
The second line with n integers, expressed sequence A;
The third line with m integers, expressed sequence B; - 输出
- For each set of test cases, output the length of the longest common subsequence of A and B, in a single line.
- 样例输入
5 41 2 6 5 41 3 5 4
- 样例输出
3
- 上传者
- TC_胡仁东
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>using namespace std;int dp[100005],g[100005];int main(){ int n,m; while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); int x; for(int i = 1; i <= n ; ++ i) scanf("%d",&x),dp[x]=i; int r = 0 ; for(int i = 1 ; i <= m ; ++ i) { scanf("%d",&x); if(dp[x]) g[r++]=dp[x]; } int p = 0 ; dp[p++] = g[0]; for(int i = 1 ; i < r ; ++ i) if(dp[p-1] < g[i]) dp[p++] = g[i]; else { x = lower_bound(dp,dp+p,g[i])-dp; dp[x] = g[i]; } printf("%d\n",p); } return 0;}
nyoj 760
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。