专栏文章

题解：P2679 [NOIP 2015 提高组] 子串

cchenyixuan18
P2679题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqcfay5
此快照首次捕获于
2025/12/04 02:31
3 个月前
此快照最后确认于
2025/12/04 02:31
3 个月前
查看原文

题解：P2679 [NOIP 2015 提高组] 子串

题目大意

给你一个字符串 AA 和 BB，求从 AA 中取出 kk 个子串，并按原顺序排好变成 BB 的方案数。

思路

通过数据和取模可以知道，这是一道动态规划题，所以我们要定义状态和转移方程。

定义状态

定义 fi,j,k,0f_{i,j,k,0} 表示 AA 用前 ii 个字符取出 kk 个子串拼接好变成 BB 前 jj 个字符且不使用 aia_i 的方案数，fi,j,k,1f_{i,j,k,1} 表示 AA 用前 ii 个字符取出 kk 个子串拼接好变成 BB 前 jj 个字符且使用 aia_i 的方案数。

状态转移

当我们不使用 aia_i 时，那么我们得到 fi,j,k,0=fi−1,j,k,0+fi−1,j,k,0f_{i,j,k,0}=f_{i-1,j,k,0}+f_{i-1,j,k,0}，因为不使用 aia_i 相当于使用 ai−1a_{i-1} 和不使用 ai−1a_{i-1}， 若们使用 aia_i，得先满足 ai=bja_i=b_j，这时候我们得出 fi,j,k,1=fi−1,j−1,k−1,0fi−1,j−1,k−1,1+fi−1,j−1,k,1f_{i,j,k,1}=f_{i-1,j-1,k-1,0}f_{i-1,j-1,k-1,1}+f_{i-1,j-1,k,1}，因为有三种情况： 跟 bjb_j 匹配，且 ai−1a_{i-1} 不使用；跟 bjb_j 匹配， 且 ai−1a_{i-1} 使用，不纳入上个子串；跟 bjb_j 匹配， 且 ai−1a_{i-1} 使用，纳入上个子串，所以我们得出状态转移方程是 fi,j,k,0=fi−1,j,k,0+fi−1,j,k,1f_{i,j,k,0}=f_{i-1,j,k,0}+f_{i-1,j,k,1} 和当 ai=bja_i=b_j 时，fi,j,k,1=fi−1,j−1,k−1,0+fi−1,j−1,k−1,1+fi−1,j−1,k,1f_{i,j,k,1}=f_{i-1,j-1,k-1,0}+f_{i-1,j-1,k-1,1}+f_{i-1,j-1,k,1}。

优化

此时我们发现空间复杂度十分高，此时我们只需要滚动优化即可。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,m,K,dp[2][205][205][2];
char A[1005],B[1005];
signed main(){
	cin>>n>>m>>K;
	for(int i=1;i<=n;i++){
		cin>>A[i];
	}
	for(int j=1;j<=m;j++){
		cin>>B[j];
	}
	dp[0][0][0][0]=dp[1][0][0][0]=1;
	bool p=0; 
	for(int i=1;i<=n;i++){
		p=!p;
		for(int j=1;j<=m;j++){
			for(int k=1;k<=K;k++){
				dp[p][j][k][0]=dp[p][j][k][1]=0;
				if(A[i]!=B[j]){
					dp[p][j][k][0]=dp[!p][j][k][0]+dp[!p][j][k][1];
				}
				else{
					dp[p][j][k][0]=dp[!p][j][k][0]+dp[!p][j][k][1];
					dp[p][j][k][1]=dp[!p][j-1][k-1][0]+dp[!p][j-1][k-1][1]+dp[!p][j-1][k][1];
				}
				dp[p][j][k][0]%=mod;
				dp[p][j][k][1]%=mod;
			}
			
		}
	}
	cout<<(dp[p][m][K][0]+dp[p][m][K][1])%mod; 
	return 0;
}
我才不告诉你我做了半年呢。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...