Description：

给两个长度为 $5n$ 字符串，求他们的最长公共子序列，保证两个字符串中的每个字符都出现了恰好五次。

$1\leqslant n\leqslant 20000$

Solution：

最长公共子序列有经典的O(n^2)做法，但是这题显然是通过不了的，也没有充分挖掘题目的性质。

$20000\times 5=100000$ ，猜想复杂度中有一个 $\log$ ，再进一步猜想是一个数据结构优化 $DP$ 。

不妨换一下状态定义： $f[i][j]$ 表示第一个串处理到了 $i$ ，第二个串的最后一个匹配位置是 $j$ 的最长公共子序列，转移为 $f[i][j]=\max(f[i-1][k]+(a[i]=b[j]))(k<j)$ ，一般来说这个转移是 $O(n^3)$ 的，但是这题既然保证了每个都出现了恰好五次，说明 $a[i]=b[k]$ 的情况其实是非常少的，那么我们就不难想到只转移 $a[i]=b[k]$ 的情况，换个思路的话也就是说如果只看 $DP$ 数组第 $2$ 维的话，这一个和上一个应该只有 $a[i]=b[k]$ 的位置 $k$ 会发生变化，所以就可以用一个树状数组来维护第 $2$ 维，第 $1$ 维滚动，注意一下循环顺序就好了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 20010

vector<int> v[MAXN];

bool cmp(int a,int b){return a > b;}

int a[MAXN * 5],b[MAXN * 5];

int lowbit(int x){return x & (-x);}

int c[MAXN * 5];

void add(int p,int x){for(int i = p;i <= 5 * n;i += lowbit(i))c[i] = max(c[i],x);return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= 5 * n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= 5 * n;++i)scanf("%d",&b[i]);

	for(int i = 1;i <= 5 * n;++i)v[b[i]].push_back(i);

	for(int i = 1;i <= 20000;++i)sort(v[i].begin(),v[i].end(),cmp);

	for(int i = 1;i <= 5 * n;++i)

	{

		for(vector<int>::iterator it = v[a[i]].begin();it != v[a[i]].end();++it)

		{

			add(*it,query(*it - 1) + 1);

		}

	}

	cout << query(5 * n) << endl;

	return 0;

}