P4303 [AHOI2006]基因匹配
标签（空格分隔）： 考试题 nt题 LCS优化
【题目】
卡卡昨天晚上做梦梦见他和可可来到了另外一个星球，这个星球上生物的DNA序列由无数种碱基排列而成（地球上只有4种），而更奇怪的是，组成DNA序列的每一种碱基在该序列中正好出现5次！这样如果一个DNA序列有N种不同的碱基构成，那么它的长度一定是5N。
卡卡醒来后向可可叙述了这个奇怪的梦，而可可这些日子正在研究生物信息学中的基因匹配问题，于是他决定为这个奇怪星球上的生物写一个简单的DNA匹配程序。
为了描述基因匹配的原理，我们需要先定义子序列的概念：若从一个DNA序列（字符串）s中任意抽取一些碱基（字符），将它们仍按在s中的顺序排列成一个新串u，则称u是s的一个子序列。对于两个DNA序列s1和s2，如果存在一个序列u同时成为s1和s2的子序列，则称u是s1和s2的公共子序列。
卡卡已知两个DNA序列s1和s2，求s1和s2的最大匹配就是指s1和s2最长公共子序列的长度。
[任务] 编写一个程序：
从输入文件中读入两个等长的DNA序列；
计算它们的最大匹配；
向输出文件打印你得到的结果。
输入格式
输入文件中第一行有一个整数N，表示这个星球上某种生物使用了N种不同的碱基，以后将它们编号为1…N的整数
以下还有两行，每行描述一个DNA序列：包含5N个1…N的整数，且每一个整数在对应的序列中正好出现5次。
输出格式
输出文件中只有一个整数，即两个DNA序列的最大匹配数目。
输入输出样例
输入1
2
1 1 1 1 1 2 2 2 2 2
1 1 1 2 2 2 2 2 1 1
输出1
8
输入2
2
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1
输出2
7
说明/提示
1≤N≤20000
【思路】
扯点别的
看此题前先观光一下前提级博客：https://www.cnblogs.com/614685877--aakennes/p/12663440.html，与本题密切相关。
考试时乍一看一个LCS板子，再一看数据范围，显然n²的效率A不了，于是乎就想起之前写过得一道题（上面那个博客），用lis优化lcs，时间效率为nlogn，但那道题显然有个限制条件：序列中所有的数都相等。这道题明确给出了重复的个数，一开始我就想用普通的5*x+cnt[x]来存，之后跟王子公主那道题一样，结果连样例都过不去（但竟然有50分），然后就摸了。
之后看到题解十分气愤，竟然真是王子公主的变种，很气。
正解
在王子公主中我们b序列中的一个数对应a序列中这个数的位置，然后对应到b序列中，最后跑一遍lis。这道题我们可以把b序列中的一个数对应到a序列中这个数的所有位置，倒序存进b序列里面。
问题1:为什么要存所有位置
表面上我们存进了所有的位置，实际上我们只需要用这些位置的某一个最优值就可以。拿样例2来说，我们倒序存入后，新数组：（1）8 6 5 2 1 |（2） 10 9 7 4 3 |（3） 10 9 7 4 3 |（4） 10 9 7 4 3 |（5） 8 6 5 2 1 |（6） 8 6 5 2 1 |（7） 10 9 7 4 3 |（8） 10 9 7 4 3 |（9） 8 6 5 2 1 |（10） 8 6 5 2 1 1，最长上升子序列的数依次来源于：第一个串的1，第二个串的3，第三个串的4，第五个串的5，第六个串的6，第七个串的7，第九个串的8。
问题2：为什么要倒序
每一个串一开始一定是一个上升的子序列，所以倒序后一定是一个下降的子序列，这样在跑lis的时候我们只会用到这个串中的一个数。相反，如果你不倒序，肯定就会用到这个串所有数，结果定然不对。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
const int maxn=1e6+5,maxe=250*250+5,INF=0x3f3f3f3f;
int n,f[maxn],a[20005][20005],b[maxn],low[maxn],cnt[maxn];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main(){
freopen("a.in","r",stdin);
// freopen("dinning.out","w",stdout);
n=read();
int maxmax=0;
memset(low,0,sizeof(low));
for(int i=1;i<=n*5;i++){
int x=read();
a[++cnt[x]][x]=i;
}//a[cnt[x]][x]表示x在第一个序列中出现第cnt[x]次的位置
memset(cnt,0,sizeof(cnt));
int len=0;
for(int i=1;i<=n*5;i++){
int x=read();
for(int j=5;j>=1;j--)b[++len]=a[j][x];//倒序存入每一个串
}
int len1=1;
low[1]=b[1];
for(int i=2;i<=len;i++){
if(low[len1]<b[i])low[++len1]=b[i];
else low[lower_bound(low+1,low+len1+1,b[i])-low]=b[i];
}
printf("%d
",len1);
}
OVER~