『JZOJ 4721』【NOIP2016提高A组模拟8.21】最长公共子序列

4721. 【NOIP2016提高A组模拟8.21】最长公共子序列

Problem

Description

DJL为了避免成为一只咸鱼，来找Johann学习怎么求最长公共子序列。
经过长时间的摸索和练习，DJL终于学会了怎么求LCS。Johann感觉DJL孺子可教，就给他布置了一个课后作业：
给定两个长度分别为$n$和$m$的序列，序列中的每个元素都是正整数。保证每个序列中的各个元素互不相同。求这两个序列的最长公共子序列的长度。
DJL最讨厌重复劳动，所以不想做那些做过的题。于是他找你来帮他做作业。

Input

第一行两个整数$n$和$m$，表示两个数列的长度。
第二行一行$n$个整数$a_1,a_2,…,a_n$，保证$1 \leq a_i \leq 10^9$ 。
第三行一行$m$个整数$b_1,b_2,…,b_m$，保证$1 \leq b_i \leq 10^9$ 。

Output

一行一个整数，表示两个数列的最长公共子序列的长度。

Sample Input

6 6 1 3 5 7 9 8 3 4 5 6 7 8

Sample Output

4

Data Constraint

对于$40\%$的数据，$n, m≤3000$
对于$100\%$的数据，$n, m≤300000$

Solution

这题连zyx都做出来了…我太弱了。。

（（其实是因为没有看清题目里面告诉了我元素互不相同。。。。。

好吧，我们只要构建一个映射

将映射$A_i \rightarrow i$用在$B$上，对$B$求$\rm LIS$即可，若$A$中没有$B_i$就直接跳过

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <cstring>
#define MAXN 300000 + 10 
using namespace std;
map <int, int> s;
int f[MAXN], n, m;
inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}
int main(int argc, char **Argv)
{
	_read(n), _read(m);
	for (register int i = 1, x; i <= n; ++i)
	{
		_read(x);
		s[x] = i;
	}
	fill(f, f + n + 1, 2147483647);
	for (register int i = 1, x; i <= m; ++i)
	{
		_read(x);
		register int t = s[x];
		if (t) *lower_bound(f, f + m, t) = t;
	}
	printf("%d\n", lower_bound(f, f + m, 2147483647) - f);
	return 0;
}

代码比较短，就是比较慢。。。。