链接：P2679 [NOIP2015 提高组] 子串。

题意

现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等？

注意：子串取出的位置不同也认为是不同的方案。

数据范围

$1≤n≤1000$ ， $1≤m≤200$ ， $1≤k≤m$ 。结果对 $10^9+7$ 取模。

题解

初始的想法是设置 $f(i,j,k)$ 表示 A 串前 $i$ 个字符里，使用了 $k$ 个子串，来匹配了 B 串前 $j$ 个字符。

所以可列出最基本的方程：

f(i,j,k)=f(i-1,j-1,k-1)+f(i-1,j-1,k)

翻译过来就是：

A 串前 $i$ 个字符里，使用了 $k$ 个子串，匹配了 B 串前 $j$ 个字符的方案数，等价于单独使用第 $i$ 个字符作为一个子串的方案数和不单独使用的方案数（包括不使用以及和前面连在一起的情况）。

但正如上文括号里所说，这个方程未能解决不使用以及和前面连在一起的问题，所以我们要添加一维（0/1 维），来表示使用了当前字符和没使用当前的字符。

所以状态转移方程变成了以下：

\begin{cases} f(i,j,k,0)=f(i-1,j,k,0)+f(i-1,j,k,1) \\ f(i,j,k,1)=f(i-1,j-1,k-1,0)+f(i-1,j-1,k,1)+f(i-1,j-1,k-1,1) & A_i=B_j \\ f(i,j,k,1)=0 & A_i\not= B_j \end{cases}

翻译是：

如果第 $i$ 位不使用，那么方案数就是：第 $i-1$ 位未使用时，前 $i-1$ 位匹配前 $j$ 位使用 $k$ 个子串 $+$ 第 $i-1$ 位使用时，前 $i-1$ 位匹配前 $j$ 位使用 $k$ 个子串。

如果第 $i$ 位使用，意味着 $a_i=b_j$ （否则方案数为 $0$ ），那么方案数就是：第 $i-1$ 位未使用而第 $i$ 位作为一个新子串 $+$ 第 $i$ 位和前面连在一起，不单独使用 $+$ 第 $i-1$ 位使用了，但第 $i$ 位仍作为一个新子串。

我们再来思考边界条件。

对于 A 子串前 $i$ （ $i\in[0,n]$ ）位，与 B 串第 $0$ 个字符皆无法匹配，那么这样使用子串数为 $0$ ，方案数皆为 $1$ 。
$ \forall i \in [0,n] $，$ f(i,0,0,0)=1 $。

由于直接开四位数组空间会炸，使用滚动数组，滚掉第一维。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=1000+10,mod=1000000007,OK=1,NO=0;
	long long f[2+10][200+10][200+10][2+10];
	//  f[ i ][ j ][ k ][i,j是否匹配];
	//  i-A串位置  j-B串位置  k-匹配数 
	long long n,m,l;
	char A[N],B[N];
	void yzmain()
	{
		int i,pre_i;
		cin>>n>>m>>l;
		cin>>A+1>>B+1;
		f[0][0][0][0]=f[1][0][0][0]=1;// f[i][0][0][0]=1 , i /in [0,n] .
		for(int pos=1;pos<=n;pos++)
		{
			i=pos&1,pre_i=(pos-1)&1;//第一维使用滚动数组滚掉
			for(int j=1;j<=m;j++)
				for(int k=1;k<=l;k++)
				{
					if(A[pos]==B[j])
						f[i][j][k][OK]=(f[pre_i][j-1][k-1][OK]+
						                f[pre_i][j-1][k][OK]+
										f[pre_i][j-1][k-1][NO])%mod;
					else f[i][j][k][OK]=0;
					f[i][j][k][NO]=(f[pre_i][j][k][NO]+
					                f[pre_i][j][k][OK])%mod;
				}
		}
		printf("%d\n",(f[n&1][m][l][OK]+f[n&1][m][l][NO])%mod);
		return;
	}	
}
int main()
{
	_yz::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/52c690f8e24e/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 动态规划

最后更新：2023-08-21, 23:18:20

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158