NC19875. [AHOI2006]基因匹配MATCH
描述
输入描述
输入文件中第一行有一个整数N，表示这个星球上某种生物使用了N种不同的碱基，以后将它们编号为1…N的整数。
以下还有两行，每行描述一个DNA序列：包含5N个1…N的整数，且每一个整数在对应的序列中正好出现5次。
输出描述
输出文件中只有一个整数，即两个DNA序列的最大匹配数目。
示例1
输入:
2 1 1 2 2 1 1 2 1 2 2 1 2 2 2 1 1 2 2 1 1
输出:
7
C++11(clang++ 3.9) 解法, 执行用时: 123ms, 内存消耗: 5092K, 提交时间: 2020-04-02 20:07:42
#include<bits/stdc++.h>
using namespace std;
int c[100020];
int a[100020];
int haha[100020];
vector<int>pos[100020];
int n,m;
void add(int x,int y)
{
for(int i=x;i<=n;i+=i&-i)
{
c[i]=max(c[i],y);
}
}
int ask(int x)
{
int re=0;
for(int i=x;i>0;i-=i&-i)
{
re=max(re,c[i]);
}
return re;
}
int main()
{
cin>>n;
n*=5;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>haha[i];
pos[haha[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
for(int j=4;j>=0;j--)
{
add(pos[a[i]][j],ask(pos[a[i]][j]-1)+1);
}
}
cout<<ask(n)<<endl;
}
C++14(g++5.4) 解法, 执行用时: 139ms, 内存消耗: 4984K, 提交时间: 2019-09-29 09:48:58
#include <bits/stdc++.h>
using namespace std;
int c[100020];
int a[100020];
int haha[100020];
vector<int>pos[100020];
int n,m;
void add(int x,int y){
for(int i=x;i<=n;i+=i&-i){
c[i]=max(c[i],y);
}
}
int ask(int x){
int re=0;
for(int i=x;i>0;i-=i&-i){
re=max(re,c[i]);
}
return re;
}
int main(){
cin>>n;
n*=5;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>haha[i];
pos[haha[i]].push_back(i);
}
for(int i=1;i<=n;i++){
for(int j=4;j>=0;j--){
add(pos[a[i]][j],ask(pos[a[i]][j]-1)+1);
}
}
cout<<ask(n)<<endl;
}