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个匹配的进行变换。两者相乘就是组合数，表明这次变换的方法数。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 using namespace std ;

 long long c[][],dp[][] ;

 char sh[],ch[] ;

 void cmn()

 {

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

         c[i][] =  ;

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

     {

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

             c[i][j] = (c[i-][j-]+c[i-][j])% ;

     }

 }

 int main()

 {

     int N,K,M ;

     cmn() ;

     while(~scanf("%d %d %d",&N,&K,&M))

     {

         scanf("%s %s",ch,sh) ;

         int cnt =  ;

         memset(dp,,sizeof(dp)) ;

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

             if(sh[i] != ch[i])

                 cnt++ ;

         dp[][cnt] =  ;

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

         {

             for(int j =  ; j <= N ; j++)

             {

                 for(int k =  ; k <= M ; k++)

                 {

                     if(j+M-*k < ) break ;

                     if(j+M-*k > N) continue ;

                     dp[i+][j+M-*k] += ((dp[i][j]%)*(c[j][k]*c[N-j][M-k]%))% ;

                 }

             }

         }

         printf("%lld\n",dp[K][]) ;

     }

     return  ;

 }

巴特西

ZOJ 3791 An Easy Game（DP）

最新文章

热门文章