M_sea

洛谷4303 [AHOI2006]基因匹配
LuoguBZOJ分析有点神仙qwq注意到“每个数正好出现5次”,这说明每个数的转移点不超过5个。把转移点搞出来,...
扫描右侧二维码阅读全文
09
2019/01

洛谷4303 [AHOI2006]基因匹配

Luogu

BZOJ

分析

有点神仙qwq

注意到“每个数正好出现5次”,这说明每个数的转移点不超过5个。

把转移点搞出来,每个数对应的转移点按倒序重排,就变成了一个长度为$25n$的序列。

然后求这个序列的最长上升子序列就行了,可以使用树状数组来优化。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,m,tot=0;
int pos[20010][6],s[20010];
int a[500010];
int f[500010];

int c[100010];
#define lowbit(x) (x&-x)
inline void add(int x,int y) {
    for (;x<=m;x+=lowbit(x)) c[x]=max(c[x],y);
}
inline int query(int x,int sum=0) {
    for (;x;x-=lowbit(x)) sum=max(sum,c[x]);
    return sum;
}

int main() {
    n=read(),m=5*n;
    for (re int i=1,x;i<=m;++i)
        x=read(),pos[x][++s[x]]=i;
    for (re int i=1,x;i<=m;++i) {
        x=read();
        for (re int j=5;j>=1;--j) a[++tot]=pos[x][j];
    }
    for (re int i=1;i<=tot;++i)
        f[i]=query(a[i]-1)+1,add(a[i],f[i]);
    int ans=0;
    for (re int i=1;i<=tot;++i) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 05 : 53 PM

发表评论