你有一个日志文件，里面记录着各种系统事件的详细信息。自然的，事件的时间戳按照严格递增顺序排列（不会有两个事件在完全相同的时刻发生）。 遗憾的是，你的系统被病毒感染了，日志文件中混入了病毒生成的随机伪事件（但真实事件的相对顺序保持不变）。备份的日志文件也被感染了，但由于病毒采用的随机感染方法，主日志文件和备份日志文件在感染后可能会变得不一样。 给出被感染的主日志和备份日志，求真实事件序列的最长可能长度。
Input 输入第一行为数据组数T (T<=100)。每组数据包含两行，分别描述感染后的主日志和备份日志。 每个日志文件的格式相同，均为一个整数n (1<=n<=1000)（代表感染后的事件总数）和n 个不超过100,000的正整数（表示感染后各事件的时间戳）。 注意，感染后可能会出现时间戳完全相同的事件。
Output 对于每组数据，输出真实事件序列的最长可能长度。
Sample Input
1 9 1 4 2 6 3 8 5 9 1 6 2 7 6 3 5 1Sample Output
3解析：最长递增公共序列（递增序列+最长公共序列）。此问题是动态规划问题，其特点为：最优解的子问题的解也是最优解。因此用两个循环逐步从子问题中找到最优解，用二维数组dp[i][j]存储子问题的最优解。
//最长递增序列 //Dp #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MX=1010;//长度限制 int dp[MX][MX];//用来存储子问题的最优解 int A[MX],B[MX];//表示两个文件 int main() { int T; cin>>T; while(T-->0) { memset(dp,0,sizeof(dp));//初始化dp数组 int a,b;//分别表示A,B的长度 cin>>a; for(int i=1;i<=a;i++) cin>>A[i];//数组从1开始 cin>>b; for(int i=1;i<=b;i++) cin>>B[i]; int count=0;//最大增长序列的长度 for(int i=1;i<=a;i++) { int Max=0;//记录a=i这一子问题的最大增长序列的长度 for(int j=1;j<=b;j++) { //当两个数组顶元素相等时，个数加一 if(A[i]==B[j]) dp[i][j]=Max+1; //否则最大增长序列的长度为前一子问题的最大增长序列的长度 else dp[i][j]=dp[i-1][j];//数组从1开始，不用担心越界 if(A[i]>B[j]) Max=max(Max,dp[i][j]); //count保证为子问题的最大增长序列的长度 count=max(count,dp[i][j]); } } cout<<count<<endl; } return 0; }