#求助关于题解的初始化问题
查看原帖
#求助关于题解的初始化问题
800062
zi_sha_le楼主2023/12/16 15:44

请问这里f[0][0][0][0]=f[1][0][0][0]=1是什么原理

#include<iostream>
#include<cstdio>
using namespace std;
int md=1000000007;
int n,m,k,f[2][222][222][2];
char a[1001],b[201];
int main()
{
	int i,j,p;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=m;i++)
		cin>>b[i];
	f[0][0][0][0]=1;
	f[1][0][0][0]=1;//初始化,否则之后都得是0
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			for(p=1;p<=k;p++)
			{
				if(a[i]==b[j])
				{
					f[i%2][j][p][1]=(f[(i-1)%2][j-1][p][1]+f[(i-1)%2][j-1][p-1][0])%md+f[(i-1)%2][j-1][p-1][1]%md;
					//f[i-1][j-1][p][1]:将当前字符纳入前一个子串,并使用前一个字符的种数 
					//f[i-1][j-1][p-1][0/1]:将当前字符纳入新子串,但不使用(使用)前一个字符的种数 
					f[i%2][j][p][1]%=md;
					f[i%2][j][p][0]=f[(i-1)%2][j][p][1]+f[(i-1)%2][j][p][0];
					//未使用该字符的种数即前一个字符使用的种数+前一个字符未使用的种数 
					f[i%2][j][p][0]%=md;
				}
				else
				{
					f[i%2][j][p][0]=f[(i-1)%2][j][p][1]+f[(i-1)%2][j][p][0];
					f[i%2][j][p][0]%=md;
					f[i%2][j][p][1]=0;//不能使用该字符
				 } 
			}
	printf("%d",(f[n%2][m][k][1]+f[n%2][m][k][0])%md);
	return 0;
}
2023/12/16 15:44
加载中...