https://www.luogu.com.cn/problem/P1439
https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338
以上两个都是特例,一个是每个元素不重复,一个是每个元素均有5个。
正确性说明参考:https://www.luogu.com.cn/article/1bcs9052
由于一般情况可能出现多个,就需要类似于上面的处理,倒序是防止一组内选取多个,多个编号是因为只要满足下标中任意一个均可。
优化可以考虑二分或者树状数组(因为离散化过,比较方便了)。
复杂度 \(O(25n\log25n)\)。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[5*N],n5,s1[N],s2[N],n,t[N][6],f[5*N],c[5*N];
void add(int x,int v){
for(;x<=n5;x+=x&-x)c[x]=max(c[x],v);
}
int sum(int x){
int res=0;
for(;x;x-=x&-x)res=max(res,c[x]);
return res;
}
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n;
n*=5;
for(int i=1;i<=n;++i)cin>>s1[i],t[s1[i]][++t[s1[i]][0]]=i;
for(int i=1;i<=n;++i){
cin>>s2[i];
for(int j=5;j;--j)
a[++n5]=t[s2[i]][j];
}
int ans;
for(int i=1;i<=n5;++i){
f[i]=sum(a[i]-1)+1;
add(a[i],f[i]);
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}
标签:51nod,luogu,s1,int,https,s2,com,模板
From: https://www.cnblogs.com/wscqwq/p/18326647