bzoj 1264: [AHOI2006]基因匹配Match (树状数组优化dp）

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1264

思路： n大小为20000*5，而一般的dp求最长公共子序列复杂度是 n*n的，所以我们必须优化。

题目说了一个数会出现5次，那么我们可以预处理得到第一个序列a[]每个数字分别在哪些位置，

因为求LCS的状态转移方程中当 s1[i-1] == s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1;只有当两个点相同时

值才会+1，我们可以对第二个序列b[]遍历一遍，对于b[i]我们可以找到它在a[]上的5个位置，这5个

位置的dp[pos]都可以被更新,状态转移方程为： dp[pos] = max(p[1] - p[pos-1]) + 1, 对于dp[1] - dp[pos]，

这段区间的最大值，我们直接用树状数组维护就好了，时间复杂度为 O(n*logn)

实现代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 2e5+;

int a[M][],c[M],dp[M],n;

void update(int x,int p){

     while(x <= n*){

     c[x] = max(c[x],p);

     x += (x&-x);

     }

}

int getsum(int x){

    int ans = ;

    while(x){

        ans = max(ans,c[x]);

        x -= (x&-x);

    }

    return ans;

}

int main()

{

    int x;

    cin>>n;

    for(int i = ;i <= n*;i ++){

        cin>>x;

        a[x][++a[x][]] = i;

    }

    for(int i = ;i <= n*;i ++){

        cin>>x;

        for(int j = ;j >= ;j --){

            int num = getsum(a[x][j]-)+;

            if(num > dp[a[x][j]]) dp[a[x][j]] = num,update(a[x][j],num);

        }

    }

    int ans = ;

    for(int i = ;i <= n*;i ++){

        ans = max(dp[i],ans);

    }

    cout<<ans<<endl;

    return ;

}

巴特西

bzoj 1264: [AHOI2006]基因匹配Match (树状数组优化dp）

最新文章

热门文章