UOJ #149 [NOIP 2015] 子串

Solution

DP+滚动数组.

DP状态

$dp[i][j][k]$: $A$的第$i$个字符和$B$的第$j$个字符匹配且该字符在第$k$个子串中的方案数.

转移方程

$dp[0][0][0]=1$

$dp[i][j][k] = dp[i-1][j-1][k] + \sum\limits _{0\le i' <i} dp[i'][j-1][k-1]$

用数组$sum[j][k]$维护转移时用到的那个和$\sum\limits _{0\le i' <i} dp[i'][j-1][k-1]$.

三维数组会MLE, 要用滚动数组优化成二维, 把第一维去掉.

Implementation

注意计算的顺序

#include <bits/stdc++.h>

using namespace std;

const int N=1005, M=205, K=205, mod=1e9+7;

int dp[M][K];

char a[N], b[N];

int sum[M][K];

int main(){

    int  n, m, K;

    scanf("%d%d%d", &n, &m, &K);

    scanf("%s%s", a+1, b+1);

    dp[0][0]=1;

    sum[0][0]=1;

    for(int i=1; i<=n; i++){

        for(int j=m; j>0; j--){

            if(a[i]!=b[j]){

                for(int k=1; k<=K; k++)

                    dp[j][k]=0;

            }

            else{

                for(int k=1; k<=K; k++){

                    dp[j][k]=(dp[j-1][k]+sum[j-1][k-1])%mod;

                    sum[j][k]+=dp[j][k];

                    sum[j][k]%=mod;

                }

            }

        }

    }

    printf("%d\n", sum[m][K]);

    return 0;

}

巴特西

UOJ #149 [NOIP 2015] 子串

Solution

Implementation

最新文章

热门文章