UVA 10635 Prince and Princess(最长公共子序列转为最长上升子序列)

题目链接：
UVA 10635 Prince and Princess
题意：
给$n,p,q$表示接下来两行会给$p+1$和$q+1$个数。每个数都不超过$n*n$，且每行的数字各不相同，所以$p和q$也满足：$1\leq p,q < n$。求两个序列最长的上升的数字相同的公共子序列的长度。
数据范围:$2\leq n \leq 250$
分析：
最长公共子序列问题。
主要分析每行的数字各不相同。所以我们可以对第一行的每个数字编一个对应的编号，用$id[t]$表示第一行的数字$t$出现的位置，如果数字$t$没有出现，那么就$id[t] =-1$。接下来对于第二行出现的数字$r$，我们其实需要知道的是它在第一行中出现的位置$id[r]$,所以我们令$data[i]=id[r]$，最后我们只需要知道$data[i]$的最长上升子序列就得到了原来两个数组的最大公共子序列。
例如，两个数字序列分别是;
$p=6\qquad 1,7,5,4,8,3,9$
$q=7\qquad 1,4,3,5,6,2,8,9$
我们对于第一行数可以得到$id[]$数组如下：
$id[1]=1,id[7]=2,id[5]=3,id[4]=4$
$id[8]=5,id[3]=6,id[9]=7$,对于其余所有没出现的数字的$id[]$通通为$-1$。
对于第二行数我们可以得到$data$数组：
$data[1]=id[1]=1$
$data[2]=id[4]=4$
$data[3]=id[3]=6$
$data[4]=id[5]=3$
$data[5]=id[6]=-1$
$data[6]=id[2]=-1$
$data[7]=id[8]=5$
$data[8]=id[9]=7$
我们求$data$数组的最长上升子序列可到:
$1\rightarrow 4\rightarrow 5 \rightarrow 7$
对应原来的两行数字是:
$1\rightarrow 4\rightarrow 8\rightarrow 9$
长度是$4$！
时间复杂度是：$O(nlog(n))$，其中 n <script type="math/tex" id="MathJax-Element-111">n</script>是第二个数字序列的长度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 300;
const int MAX_M = 100010;int T, n, p, q, cases = 0;
int id[MAX_M], data[MAX_M], arr[MAX_M];int main()
{scanf("%d", &T);while(T--) {memset(id, -1, sizeof(id));scanf("%d%d%d", &n, &p, &q);for(int i = 1; i <= p + 1; ++i) {int t;scanf("%d", &t);id[t] = i;}for(int i = 1; i <= q + 1; ++i) {int t; scanf("%d", &t);data[i] = id[t];}int len = 0;for(int i = 1; i <= q + 1; ++i) {if(data[i] == -1) continue;int pos = lower_bound(arr, arr + len, data[i]) - arr;len = max(len, pos + 1);arr[pos] = data[i];}printf("Case %d: %d\n", ++cases, len);}return 0;
}