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

· · 题解

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

题目大意

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

思路

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

定义状态

定义 f_{i,j,k,0} 表示 A 用前 i 个字符取出 k 个子串拼接好变成 B 前 j 个字符且不使用 a_i 的方案数，f_{i,j,k,1} 表示 A 用前 i 个字符取出 k 个子串拼接好变成 B 前 j 个字符且使用 a_i 的方案数。

状态转移

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

优化

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

代码

#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;
}

我才不告诉你我做了半年呢。