1264: [AHOI2006]基因匹配Match
题目：传送门
简要题意：
给出两个序列。每个序列都由n种不同的数字组成，保证每个序列种每种数字都会出现5次（位置不一定一样），也就是序列长度为5*n啦。
求这两个序列的最长公共子序列。
题解：
假的（nlogn）最长公共子序列算法
本蒟蒻看完题：
woc！大水题，这不是就是动态规划求最长公共子序列吗~
看完数据范围...ORZ那么大！！！最长公共子序列的基础算法要（n^2）...完了...不会...瞎搞？？？
这么皮，怎么破！
tkj神犇：so easy~~（orz...%%%）
好的，%完师兄...
真正的正解：
本题的突破口其实就在于每种数只出现5次。
那么我们可以先把第一个数列种每种数出现的位置用pos[]记录，然后放到第二个数列。
举个栗子，就拿样例来说：
第一个：1 1 2 2 1 1 2 1 2 2
那么pos[1]=1,2,5,6,8 pos[2]=3,4,7,9,10
然后放回第二个数列：1 2 2 2 1 1 2 2 1 1
用一个新的s[]记录新数列，s[]=8 6 5 2 1,10 9 7 4 3, 10 9 7 4 3...(以此类推)
那么我们只需要求出这个新数列的最长上升子序列就ok啦~（原理十分简单，模拟一下就ok）
这里还有一个小细节需要注意：不难发现，我们更新新数列的时候每种数字的位置都是按倒序放的，这样就可以避免在第二个数列中的一个位置重复选择（重点）。
好啦，这样子时间复杂度就为（nlongn）
但是...是假的...因为要是每种数不止出现五次...那就ORZ吧！
AC代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define qread(x)x=read();
using namespace std;
inline int read()
{
int f=,x=;char ch;
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return f*x;
}
struct node1
{
int pos[],id;
node1(){id=;}
}a[];
struct node2
{
int pos[],id;
node2(){id=;}
}b[];
int s[];
int n,N,len;
bool cmp(int n1,int n2)
{
return n1>n2;
}
int f[];//表示长度为i的最长上升子序列的末尾（最小）
int erfen(int x)
{
int l=,r=len,ans=;
while(l<=r)
{
int mid=(l+r)/;
if(f[mid]>=s[x])
{
ans=mid;
r=mid-;
}
else l=mid+;
}
return ans;
}
int main()
{
qread(n);
for(int i=;i<=n*;i++)
{
int x;qread(x);
a[x].id++;
a[x].pos[a[x].id]=i;
}
for(int i=;i<=n;i++)sort(a[i].pos+,a[i].pos++);
for(int i=;i<=n*;i++)
{
int x;qread(x);
int k;
k=a[x].id;
for(int j=i*-;j<=i*;j++)
{
s[j]=a[x].pos[k];
k--;
}
}
N=n*;
f[]=s[];len=;
for(int i=;i<=N;i++)
{
if(s[i]>f[len])
f[++len]=s[i];
else
{
int j=erfen(i);
f[j]=s[i];
}
}
printf("%d\n",len);
return ;
}