[dp]zoj 3791

大致题意

给出两个长度为n的01串，每次可以修改第一个串中m个字符，问在第k次可以把第一个串改成第二个串的方法有多少种

 

大致思路：

      挺明显的水dp，dp[i][j]为第i步两个字符串中不同的字符个数为j的方法的种类数。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
ll mod=1000000009;
ll dp[110][110],c[110][110];
void init(){
    c[0][0]=1;
    for(int i=1;i<=109;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
}
char str1[110],str2[110];
int main(){
    int i,j,k,nk,m,n,a,b,d;
    init();
    while(scanf("%d%d%d",&n,&nk,&m)!=EOF){
        scanf("%s%s",str1,str2);
        for(i=0,a=0;i<n;i++){
            if(str1[i]!=str2[i])a++;
        }
        memset(dp,0,sizeof(dp));
        dp[0][a] = 1;
        for(i=1;i<=nk;i++){
            for(j=0;j<=n;j++){
                for(k=max(0,j-m);k<=min(n,j+m);k++){
                    if(k<=j){
                        b=j-k;
                        if((m+b)%2==1)continue;
                        d=(m+b)/2;
                        if(d>n-k||m-d>k)continue;
                        dp[i][j]=(dp[i][j]+((c[k][m-d]*c[n-k][d])%mod)*dp[i-1][k]%mod)%mod;
                    }else if(k>j){
                        b=k-j;
                        if((m+b)%2==1)continue;
                        d=(m+b)/2;
                        if(d>k||m-d>n-k)continue;
                        dp[i][j]=(dp[i][j]+((c[k][d]*c[n-k][m-d])%mod)*dp[i-1][k]%mod)%mod;
                    }
                }
            }
        }
        printf("%lld\n",dp[nk][0]);
    }
    return 0;
}