online 最长 problem string cpp name pan ont
给出两个长度为 5*n 的序列,每个序列中,有 1~n 各 5 个。
求其最长公共子序列长度。
我们发现这题的序列特殊性是关键!
我们只需要知道每一种数字在某一个序列中的 5 个位置,然后对于普通的 LCS 问题,我们只有在 a[i] = b[j] 的时候才会 + 1。
那么我们可以维护一个树状数组,在 a 序列中,我们一个一个位置扫过去,每次通过树状数组维护的前缀最大值来更新,然后因为修改不多,所以维护最大值是可以的。
这样,修改 logn,查询 logn,可以承受了。
- #include <cstring>
- #include <algorithm>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <vector>
- using namespace std;
- const int N=20000+5,M=N*5;
- int n,m,a[M],cnt[N],v[N][5];
- int c[M],dp[M];
- int lowbit(int x){
- return x&-x;
- }
- int ask(int x){
- int ans=0;
- for (;x>0;x-=lowbit(x))
- ans=max(ans,c[x]);
- return ans;
- }
- void change(int x,int d){
- for (;x<=m;x+=lowbit(x))
- c[x]=max(c[x],d);
- }
- int main(){
- scanf("%d",&n);
- m=n*5;
- for (int i=1;i<=m;i++)
- scanf("%d",&a[i]);
- memset(cnt,0,sizeof cnt);
- for (int i=1,x;i<=m;i++){
- scanf("%d",&x);
- v[x][cnt[x]++]=i;
- }
- memset(c,0,sizeof c);
- memset(dp,0,sizeof dp);
- for (int i=1;i<=m;i++)
- for (int j=4;j>=0;j--){
- int pos=v[a[i]][j];
- dp[pos]=max(dp[pos],ask(pos-1)+1);
- change(pos,dp[pos]);
- }
- int ans=0;
- for (int i=1;i<=m;i++)
- ans=max(ans,dp[i]);
- printf("%d",ans);
- return 0;
- }
BZOJ1264 [AHOI2006] 基因匹配 Match 动态规划 树状数组
来源: http://www.bubuko.com/infodetail-2274101.html