BZOJ 1264 AHOI 2006遺伝子マッチングMatchダイナミックプランニング+ツリー配列
1117 ワード
n個の数と2個の長さのn*5の序列を与えて、それぞれの数はちょうど5回現れて、2個の序列のLCSを求めます
n<=20000、シーケンス長は10 W、地味な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)
難しい問題ですが、難しくはありません.
n<=20000、シーケンス長は10 W、地味な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;
}