ZOJ 3791 An Easy Game

思路：dp+记忆化搜索，设dp[n][m]表示s1与s2不同字符个数为n，还需要变m步的方法数，那么:

dp[n][m] = (c[n][i]*c[N-n][K-i]) * dp[n-i+(K-i)][m-1] (i需满足数组下标不小0)。c数组表示组合数。

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MOD 1000000009

const int MAXN = 101;

using namespace std;

long long int dp[MAXN][MAXN], c[MAXN][MAXN], N, M, K;

void init(){

    c[0][0] = 1, c[1][0] = 1, c[1][1] = 1;

    for(int i = 2; i < MAXN; i ++){

        c[i][0] = 1;

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

            c[i][j] = c[i-1][j-1] + c[i-1][j];

            if(c[i][j] >= MOD) c[i][j] %= MOD;

        }

    }

}

int dfs(int n, int m){

    if(dp[n][m] != -1) return dp[n][m];

    if(m == 0) return dp[n][m] = (n == 0);

    dp[n][m] = 0;

    for(int i = 0; i <= K; i ++){

        if(n < i || N - n < K - i) continue;

        dp[n][m] += (((c[n][i] * c[N-n][K-i]) % MOD) * dfs(n - i + (K - i), m-1))%MOD;

        dp[n][m] %= MOD;

    }

    return dp[n][m];

}

int main(){

    string s1, s2;

    init();

    while(cin >> N >> M >> K){

        cin >> s1 >> s2;

        int cnt = 0;

        for(int i = 0; i < N; i ++)

            if(s1[i] != s2[i]) cnt ++;

        memset(dp, -1, sizeof dp);

        printf("%d\n", dfs(cnt, M));

    }

    return 0;

}

巴特西

ZOJ 3791 An Easy Game

最新文章

热门文章