首页 > 代码库 > 第一轮 D
第一轮 D
Virus
Time Limit:1000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Submit Status
Description
Download as PDF
Virus
We have a log file, which is a sequence of recorded events. Naturally, the timestamps are strictly increasing.
However, it is infected by a virus, so random records are inserted (but the order of original events is preserved). The backup log file is also infected, but since the virus is making changes randomly, the two logs are now different.
Given the two infected logs, your task is to find the longest possible original log file. Note that there might be duplicated timestamps in an infected log, but the original log file will not have duplicated timestamps.
Input
The first line contains T ( T$ \le$100), the number of test cases. Each of the following lines contains two lines, describing the two logs in the same format. Each log starts with an integer n ( 1$ \le$n$ \le$1000), the number of events in the log, which is followed by n positive integers not greater than 100,000, the timestamps of the events, in the same order as they appear in the log.
Output
For each test case, print the number of events in the longest possible original log file.
Sample Input
1
9 1 4 2 6 3 8 5 9 1
6 2 7 6 3 5 1
Sample Output
Time Limit:1000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Submit Status
Description
Download as PDF
Virus
We have a log file, which is a sequence of recorded events. Naturally, the timestamps are strictly increasing.
However, it is infected by a virus, so random records are inserted (but the order of original events is preserved). The backup log file is also infected, but since the virus is making changes randomly, the two logs are now different.
Given the two infected logs, your task is to find the longest possible original log file. Note that there might be duplicated timestamps in an infected log, but the original log file will not have duplicated timestamps.
Input
The first line contains T ( T$ \le$100), the number of test cases. Each of the following lines contains two lines, describing the two logs in the same format. Each log starts with an integer n ( 1$ \le$n$ \le$1000), the number of events in the log, which is followed by n positive integers not greater than 100,000, the timestamps of the events, in the same order as they appear in the log.
Output
For each test case, print the number of events in the longest possible original log file.
Sample Input
1
9 1 4 2 6 3 8 5 9 1
6 2 7 6 3 5 1
Sample Output
3
最长公共子序列匹配
/************************************************************************* > File Name: e.cpp > Author:yuan > Mail: > Created Time: 2014年11月09日 星期日 16时37分18秒 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int a[1007],b[1007],dp[1007]; int t,n,m; int main() { scanf("%d",&t); while(t--){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=0;i<m;i++) scanf("%d",&b[i]); for(int i=0;i<n;i++) { int MAX=0; for(int j=0;j<m;j++) { if(a[i]==b[j]){ dp[j]=MAX+1; } if(a[i]>b[j]&&MAX<dp[j]){ MAX=dp[j]; } } } int ans=0; for(int i=0;i<m;i++) ans=max(ans,dp[i]); printf("%d\n",ans); } return 0; }
第一轮 D
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。