【CodeCraft赛事】Problem 7——X-man(最长公共子串LCS变种）

【CodeCraft比赛】Problem 7——X-man(最长公共子串LCS变种）

题目：点击打开链接

Question 7

Problem Statement

Dr. Charles Xavier is trying to check the correlation between the DNA samples of Magneto and Wolverine. Both the DNAs are of length N, and can be described by using all integers between 1 to N exactly once. The correlation between two DNAs is defined as the Longest Common Subsequence of both the DNAs.
Help Dr. Xavier find the correlation between the two DNAs.

Input :

First line of input contains number of Test Cases T.
ach test case starts with an integer N, size of DNA.
Next two lines contains N integers each, first line depicting the sequence of Magneto's DNA and second line depicting Wolverine's DNA.

Output :

For each test case print one integer, the correlation between the two DNAs.

Sample Input :

221 22 131 2 31 3 2

Sample Output :

12

Constraints :1 ≤ T ≤ 10 
1 ≤ N ≤ 100000 
Memory Limit : 32 MB 
Time Limit : 2s

这个题在题干里的描述便基本说明了是LCS，但如果不注意细节的话会掉入陷阱不能自拔，徒增TLE。

首先，我们知道LCS的一般解法是DP，公式如下。

但是首先应该注意到这个题的数据规模——100000，如果是十万的话，二维数组是不可以的，编译的时候便会提示数组过大。所以使用《算法设计与信息学竞赛》中的思想。用一个滚动的一位数组代替原二维数组，写出如下代码，但是仍然TLE。

#include<stdio.h>#include<string.h>  const int MAX = 100001; int A[MAX]; int B[MAX];  int main() {     int t;     int p;     int q;     int res;     scanf("%d", &t);      while (t--)     {         int x;         int provi[MAX];         scanf("%d", &p);          memset(provi, 0, sizeof(provi));          for (int i=1; i<=p; i++)         {             scanf("%d", &x);             provi[x] = i;         }         int k = 0;         for (int i=1; i<=p; i++)         {             scanf("%d", &x);             if (provi[x] != 0)             {                 A[k++] = provi[x];             }         }         B[0] = A[0];         res = 1;         for (int i=1; i<k; i++)         {             int left = 0;             int right = res;             while (left < right)             {                 int mid = (left + right) / 2;                 if (A[i] > B[mid])                 {                     left = mid + 1;                 }                 else                 {                     right = mid;                 }             }             B[left] = A[i];             if (left >= res)             {                 res++;             }         }         printf("%d\n", res);     }     return 0; }