Match 基因匹配题解(From luoguBlog)

N<=20000！\(N^2\)的LCS要原地爆炸。

去您妈的优化考场上有分就行TLE60挺值了嘿嘿嘿

然而这显然是个板子只不过像我这样见识短浅的蒟蒻不知道罢了

其实就是优化lcs

正解:

转化为lis后二分复杂度nlogn。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int n,s1[100010],s2[100010],pos[20010][8],num[20010]={0};

int tot=0,res[500010];

int ans=1,f[500010];

int main()

{

	//freopen("lis.out","w",stdout);

	cin>>n;

	n*=5;

	for(int i=1;i<=n;i++)scanf("%d",&s1[i]);

	for(int i=1;i<=n;i++)scanf("%d",&s2[i]),pos[s2[i]][++num[s2[i]]]=i;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=5;j++)res[++tot]=pos[s1[i]][5-j+1];

	/*cout<<endl;

	for(int i=1;i<=tot;i++)cout<<res[i]<<' ';

	cout<<endl;*/

    f[1]=res[1];

    for(int i=2;i<=tot;i++)

    {

    	if(res[i]>f[ans])

    	{

    		ans++;

    		f[ans]=res[i];

    	}

    	else

    	{

    		int loc=lower_bound(f+1,f+ans+1,res[i])-f;

    		f[loc]=res[i];

    	}

    }

	cout<<ans<<endl;

	return 0;

}

巴特西

Match 基因匹配题解(From luoguBlog)

最新文章

热门文章

巴特西

Match 基因匹配 题解(From luoguBlog)

最新文章

热门文章

Match 基因匹配题解(From luoguBlog)