首页 > 代码库 > BZOJ 1264 AHOI2006 基因匹配Match 动态规划+树状数组
BZOJ 1264 AHOI2006 基因匹配Match 动态规划+树状数组
题目大意:给定n个数和两个长度为n*5的序列,每个数恰好出现5次,求两个序列的LCS
n<=20000,序列长度就是10W,朴素的O(n^2)一定会超时
所以我们考虑LCS的一些性质
LCS的决策+1的条件是a[i]==b[j] 于是我们记录a序列中每个数的5个位置
扫一下b[i] 对于每个b[i]找到b[i]在a中的5个位置 这5个位置的每个f[pos]值都可以被b[i]更新 于是找到f[1]到f[pos-1]的最大值+1 更新f[pos]即可
这个用树状数组维护 时间复杂度O(nlogn)
很难想的一道题 不过不难写
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 200200 using namespace std; int n,ans,a[M*5],b[M*5],c[M*5],f[M*5],pos[M][6]; void Update(int x,int y) { for(;x<=n*5;x+=x&-x) c[x]=max(c[x],y); } int Get_Ans(int x) { int re=0; for(;x;x-=x&-x) re=max(re,c[x]); return re; } int main() { int i,j; cin>>n; for(i=1;i<=n*5;i++) { scanf("%d",&a[i]); pos[ a[i] ][ ++pos[a[i]][0] ]=i; } for(i=1;i<=n*5;i++) scanf("%d",&b[i]); for(i=1;i<=n*5;i++) { for(j=5;j;j--) { int k=pos[b[i]][j]; f[k]=max( f[k] , Get_Ans(k-1)+1 ); Update(k,f[k]); ans=max(ans,f[k]); } } cout<<ans<<endl; }
BZOJ 1264 AHOI2006 基因匹配Match 动态规划+树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。