前言

感觉这几篇仅有的题解都没说清楚，并且有些还是错的，我再发一篇吧。

分析

首先lcs（最长公共子序列）肯定是板子。但这题要求我们不能光记lcs是怎么打的，因为没这部分分，并且另外一个方程的转移要用到状态的定义。在此定义状态：

设题设字符串为$S$,$T$,然后定义字符串的前缀$i$表示字符串开头至$i$位置构成的字符串,例如$S$的前缀$i$表示$S_1\sim S_i$。

$f(i,j)$表示$S$的前缀$i$和$T$的前缀$j$的lcs的长度，根据广为人知的lcs算法,

\[f(i,j)=\max\left\{f(i-1,j),f(i,j-1),(f(i-1,j-1)+1)*[S_i==T_j]\right\}
\]

前两个转移式子表示不匹配$S_i$和$T_j$，最后的式子表示$S_i$和$T_j$匹配并将其贡献计入答案。

考虑新状态$g(i,j)$表示同上解释的lcs的匹配方式对数。那么如何转移呢？首先若$f(i,j)$等于不匹配转移式子，那么就不匹配转移式子对应的$g$应计入答案，因为若$f$不改变，那么匹配方式及其对数也应不变。然后考虑两种特殊情况：

\[f(i,j)=f(i-1,j-1)\&S_i\neq T_j$$它描述的是$S_i$和$T_j$都不做出贡献而直接转移重复的情况，那么根据容斥原理，就应减去$g(i-1,j-1)$。
\]

复杂度

时间是$O(n\cdot m)$的，没问题。但是朴素代码空间复杂度也是$O(n\cdot m)$的，128MB要炸空间，于是要用滚动数组。

代码

借鉴kiddingme12138的，他的代码（以及很多人的）虽然能AC但是有错，即特殊情况2中无论$f(i,j)$最终是否等于$f(i-1,j-1)+1$只要$S_i=T_j$那么就加上$g(i-1,j-1)$。望加强数据。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#define rg register

using namespace std;

const int MAXN=5e3+7;

const int mod=1e8;

int n,m;

char S[MAXN],T[MAXN];

int f[2][MAXN],g[2][MAXN];

int main()

{

//	freopen("lcs.in","r",stdin);

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

	scanf("%s",S+1);

	n=strlen(S+1)-1;

	scanf("%s",T+1);

	m=strlen(T+1)-1;

	int cur=0;

	for(rg int i=0;i<=m;++i)

		g[cur][i]=1;

	for(rg int i=0;i<=n;++i)

	{

		cur^=1;g[cur][0]=1;

		for(rg int j=1;j<=m;++j)

		{

			g[cur][j]=0;

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

			if(S[i]==T[j])

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

			if(f[cur][j]==f[cur^1][j])

				g[cur][j]+=g[cur^1][j];

			if(f[cur][j]==f[cur][j-1])

				g[cur][j]+=g[cur][j-1];

			if(S[i]==T[j]&&f[cur][j]==f[cur^1][j-1]+1)

				g[cur][j]+=g[cur^1][j-1];

			if(S[i]!=T[j]&&f[cur][j]==f[cur^1][j-1])

				g[cur][j]-=g[cur^1][j-1];

			g[cur][j]=(g[cur][j]+mod)%mod;

		}

	}

	printf("%d\n%d",f[cur][m],g[cur][m]);

}

巴特西

LG2516 【[HAOI2010]最长公共子序列】

前言

分析

复杂度

代码

最新文章

热门文章