• 欢迎光临~

P4303 [AHOI2006]基因匹配

开发技术 开发技术 2022-10-05 次浏览

初始方程为:

[f_{i,j}= max (f_{i-1,j-1}+1,f_{i-1,j},f_{i,j-1}) ]

对于每一个 (i) 来说,只有五次由 (f_{i-1,j-1}) 来转移(组成DNA序列的每一种碱基在该序列中正好出现5次) 。

其他的可以是由上方的数字(拷贝)或左边的所有数字的最大值( (1--n) 的最值)来转移。

考虑去除 (j) 的一维,

对于不需要由 (f_{i-1,j-1}) 来转移的 (f[j]) ,不变(因为改变会增加时间复杂度,就退化为初始的方程了)。

我们用树状数组来维护最大值 (O(log n)) ,并逆序转移(类似于背包问题)。

因为最大值可以通过向下和向右转移来到 (f_{i-1,j-1}) 来转移 (f_{i,j})

其他大佬的解释(蒟蒻溴化氢)

P4303 [AHOI2006]基因匹配

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,ans;
int c[N],a[N];
int b[N],num[N][6];
int f[N];
int tot[N];
int lowbit(int x){
	return x&(-x);
}
int query(int x){
	int res=0;
	for(; x; x-=lowbit(x))res=max(res,c[x]);
	return res;
}
void update(int x,int y)
{
	for(; x<=n; x+=lowbit(x))c[x]=max(c[x],y);
	return;
}
int main()
{
	cin>>n;n*=5;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	for(int i=1; i<=n; i++)
	{
		cin>>b[i];
		num[b[i]][++tot[b[i]]]=i;
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=5; j>=1; j--)
		{
			static int x;
			x=num[a[i]][j];
			f[x]=query(x-1)+1;
			update(x,f[x]);
		}
	}
	for(int i=1; i<=n; i++)ans=max(ans,f[i]);
	cout<<ans<<endl;
}
程序员灯塔
转载请注明原文链接:P4303 [AHOI2006]基因匹配
喜欢 (0)