ZOJ 3791 An Easy Game（DP）

题意：给你两个长度为N的字符串，将第一个字符串每次只能变化M个，问变换K次之后变成第二个字符串一共有几种方法。

思路： DP。dp[i][j]表示变了 i 次之后有j个不一样的字母的方法数。

状态转移方程：dp[i+1][j+M-2*k] += (dp[i][j]*(c[j][k]*c[N-j][M-k]) ;

c[j][k]表示的是从j个不匹配的字符中找出k个不匹配，所以c[N-j][M-k]表示的剩下的N-j个中挑出M-k个匹配的进行变换。两者相乘就是组合数，表明这次变换的方法数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 
 5 using namespace std ;
 6 
 7 long long c[110][110],dp[110][110] ;
 8 char sh[110],ch[110] ;
 9 
10 void cmn()
11 {
12     for(int i = 0 ; i < 110 ; i++)
13         c[i][0] = 1 ;
14     for(int i = 1 ; i < 110 ; i++)
15     {
16         for(int j = 1 ; j <= i ; j++)
17             c[i][j] = (c[i-1][j-1]+c[i-1][j])%1000000009 ;
18     }
19 }
20 int main()
21 {
22     int N,K,M ;
23     cmn() ;
24     while(~scanf("%d %d %d",&N,&K,&M))
25     {
26         scanf("%s %s",ch,sh) ;
27         int cnt = 0 ;
28         memset(dp,0,sizeof(dp)) ;
29         for(int i = 0 ; i < N ; i++)
30             if(sh[i] != ch[i])
31                 cnt++ ;
32         dp[0][cnt] = 1 ;
33         for(int i = 0 ; i < K ; i++)
34         {
35             for(int j = 0 ; j <= N ; j++)
36             {
37                 for(int k = 0 ; k <= M ; k++)
38                 {
39                     if(j+M-2*k < 0) break ;
40                     if(j+M-2*k > N) continue ;
41                     dp[i+1][j+M-2*k] += ((dp[i][j]%1000000009)*(c[j][k]*c[N-j][M-k]%1000000009))%1000000009 ;
42                 }
43             }
44         }
45         printf("%lld
",dp[K][0]) ;
46     }
47     return 0 ;
48 }

View Code