dp+树状数组bzoj1264AHOI2006基因匹配

这个题嘛。。。

算是一个好题吧，如果能想到的话很快就能A掉

但是。。。。对于我不行

首先说做法吧，显然是从每个字母都出现了5次入手的，从这一点我们就想到当求LCS的时候，决策&＃43;1当且仅当两个对应字符相等（废话。。。。）

所以做法就明显了：依次循环第一个字符串的每个位置，循环到第i个字符时，设该字符在第二个字符串出现的位置为p1~p5，设F[x]表示LCS(i,x)。倒序循环p5~p1，用Max{F[1]~F[pk-1]}&＃43;1更新F[pk]。

但是！

直接选决策会T ，所以我们就要选用一种又快又好写的数据结构——树状数组，用于维护区间前缀的最大&＃20540;，其实挺好写的

但是由于本人有树状数组恐惧症，所以一开始写的是线段树，然后果断TLE了！！

最后实在没办法还是写了树状数组，这东西确实快啊。。。可是我就是不想写。。。。。

#include
#include
#include
#include
#define MAX 100000
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int a[MAX],b[MAX],c[MAX*4];
int n,m,f[MAX]={0},x[MAX][6],y[MAX][6];
int ask_max(int x)
{
int Max=0;
for(int i=x;i>0;i-=i&(-i))
Max=max(Max,c[i]);
return Max;
}
void change(int pos,int number)
{
for(int i=pos;i<=n;i+=i&(-i))
c[i]=max(c[i],number);
return;
}
int main()
{
scanf("%d",&n);
m=n,n*=5;
rep(i,1,n)
scanf("%d",&a[i]);
rep(i,1,n)
scanf("%d",&b[i]),y[b[i]][++y[b[i]][0]]=i;
memset(c,0,sizeof(c));
rep(i,1,n)
{
for(int j=5;j>=1;j--)
f[y[a[i]][j]]=ask_max(y[a[i]][j]-1)+1,change(y[a[i]][j],f[y[a[i]][j]]);
}
printf("%d\n",ask_max(n));
return 0;
}

dp+树状数组 bzoj1264 AHOI2006基因匹配,布布扣,bubuko.com