P4303 [AHOI2006]基因匹配 未完成

时间：2021-10-17 16:58:06

题目

luogu

暴力60pts部分

显然如果没有出现次数==5的条件

显然是\(N_{2}\)的求lcs的模板

但是加点条件就完全不同了

思路

这个题短小精悍，不想数据结构那么傻逼无脑

我们考虑一下\(N_{2}\)的缺点

首先我们知道，只有a[i]==b[j]的时候

才会对答案有所贡献(先不管他是不是和他匹配的)

然后这类的匹配只有5个，而你却全部枚举一遍，岂不是很浪费时间

我们用个vector或者开个数组

依次记录b数组一个数出现的位置

枚举a数组，然后和他匹配的数字只有五个

所以在他之前的不相等只是取最大值，并没有改变最大值

所以用树状数组维护一下修改和查询

ps:树状数组维护的是到b[i]之前的最大值?还是不太懂，太笨了

暴力&&代码

#include <cstdio>

#include <iostream>

#define FOR(i,a,b) for(int i=a;i<=b;++i)

#define ll long long

using namespace std;

const int inf = 0x3f3f3f3f;

const int maxn = 1e5 + 7;

int read() {

	int x = 0, f = 1; char s = getchar();

	for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;

	for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

	return x * f;

}

int n, m;

int a[maxn], b[maxn];

int f[5007][5007];

int main() {

	n = read();

	m = n * 5;

	FOR(i, 1, m) a[i] = read();

	FOR(i, 1, m) b[i] = read();

	FOR(i, 1, m) FOR(j, 1, m) {

		if (a[i] == b[j])

			f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);

		f[i][j] = max(f[i][j], max(f[i][j - 1], f[i - 1][j]));

	}

	cout << f[m][m] << "\n";

	return 0;

}
#include <iostream>

#include <cstdio>

#include <algorithm>

#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;++i)

#define FORR(i,a,b) for(int i=a;i>=b;--i)

using namespace std;

const int maxn=1e5+7;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=(x<<1)+(x<<3)+s-'0';

	return x*f;

}

int n,a[maxn],b[maxn],jl[maxn][6],sum[maxn];

inline int lowbit(int x) {return x&-x;}

inline void modify(int x,int data) {

	for(int i=x;i<=n;i+=lowbit(i))

		sum[i]=max(sum[i],data);

}

inline int query(int x) {

	int ans=0;

	for(int i=x;i>=1;i-=lowbit(i))

		ans=max(ans,sum[i]);

	return ans;

}

int main() {

	n=read()*5;

	FOR(i,1,n) a[i]=read();

	FOR(i,1,n) b[i]=read();

	FOR(i,1,n) jl[b[i]][++jl[b[i]][0]]=i;

	FOR(i,1,n)

		FORR(k,5,1) { // 倒着枚举不影响后面

			int j=jl[a[i]][k];

		    modify(j,query(j-1)+1);

		}

	cout<<query(n)<<"\n";

	return 0;

}

相关文章