自动搬运

查看原文

来自洛谷，原作者为

	Coros_Trusds AFO

搬运于2025-08-24 22:35:12，当前版本为作者最后更新于2022-02-05 15:37:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验

$\rm DP$ 好题。

题目大意

给定三个数字串 $A,B,C$，请找到一个 $A,B$ 的最长公共子序列，满足 $C$ 是该子序列的子串。

题目分析

本题解中数组下标均从 $1$ 开始。

初见此题，我们对答案毫无头绪，不妨考虑答案是由什么构成的。

我们枚举 $C$ 在 $A,B$ 中的位置，再加上前后各自的最长公共子序列长度。

设 $n,m,k$ 分别表示 $A,B,C$ 序列的长度。

令 $dp1[i][j]$ 表示 $a[1\dots i]$ 和 $b[1\dots j]$ 的最长公共子序列长度，$dp2[i][j]$ 表示 $a[i\dots n]$ 和 $b[j\dots m]$ 的最长公共子序列长度。

我们先处理出 $dp1$ 和 $dp2$，处理步骤见 $\verb!P1439!$。

特别地，当 $C$ 序列的长度为 $0$ 时，答案为 $dp1[n][m]$。（$20$ 分到手了）

好了，现在答案中“前后各自的最长公共子序列长度”求出来了。

处理出 $ta$ 和 $tb$ 数组，$ta[i]$ 表示 $C$ 是否在 $a[i\dots n]$ 中出现（不一定连续），如果出现了的话 $ta[i]$ 存储 $C$ 的最后一个元素在 $A$ 中的下标，否则为 $0$。

$tb[i]$ 表示 $C$ 是否在 $b[i\dots m]$ 中出现（不一定连续），如果出现了的话 $tb[i]$ 存储 $C$ 的最后一个元素在 $B$ 中的下标，否则为 $0$。

最后答案即为 $\max\{dp1[i-1][j-1]+k+dp2[ta[i]+1][tb[j]+1]\}(1\le i\le n,1\le j\le m)$。

代码

const int ma=3e3+5;

int a[ma],b[ma],c[ma];

int ta[ma],tb[ma];

int dp1[ma][ma],dp2[ma][ma];
//dp1[i][j]:LCS(a[1...i],b[1...j])
//dp2[i][j]:LCS(a[i...n],b[j...m])

int n,m,k;

inline void work1()
{
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=m;j++)
		{
			if(a[i]==b[j])
			{
				dp1[i][j]=dp1[i-1][j-1]+1;
			}

			else
			{
				dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1]);
			}
		}
	}

	if(k==0)
	{
		printf("%d\n",dp1[n][m]);

		exit(0);
	}
}

inline void work2()
{
	for(register int i=n;i>=1;i--)
	{
		for(register int j=m;j>=1;j--)
		{
			if(a[i]==b[j])
			{
				dp2[i][j]=dp2[i+1][j+1]+1;
			}

			else
			{
				dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1]);
			}
		}
	}
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

	n=read();Input_Int(n,a);

	m=read();Input_Int(m,b);

	k=read();Input_Int(k,c);

	work1(),work2();

	for(register int i=1;i<=n;i++)
	{
		for(register int j=i,t=1;j<=n;j++)
		{
			if(a[j]==c[t])
			{
				t++;
			}

			if(t>k)
			{
				ta[i]=j;

				break;
			}
		}
	}
	
	for(register int i=1;i<=m;i++)
	{
		for(register int j=i,t=1;j<=m;j++)
		{
			if(b[j]==c[t])
			{
				t++;
			}

			if(t>k)
			{
				tb[i]=j;

				break;
			}
		}
	}

	int ans=-1;

	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=m;j++)
		{
			if(ta[i]!=0 && tb[j]!=0)//如果没出现就别考虑了
			{
				ans=max(ans,dp1[i-1][j-1]+k+dp2[ta[i]+1][tb[j]+1]);
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}

题外话

各位读者 dalao 如果觉得这篇文章有用不妨点个赞吧qwq。