首页 > 代码库 > ZOJ 3791 An easy game DP+组合数

ZOJ 3791 An easy game DP+组合数

2024-07-16 19:00:06   218人阅读

给定两个01序列，每次操作可以任意改变其中的m个数字 0变 1  1 变 0，正好要变化k次，问有多少种变法

dp模型为dp[i][j]，表示进行到第i次变化，A,B序列有j个不同的 变法总和。

循环k次，每次针对m，向那j个不同 分1-j个即可，不过要用到组合数，因为对每个数操作不同都不一样

最后结果就是 dp[k][0]

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL long longusing namespace std;LL dp[110][110];LL c[110][110];int n,m,k,len;char s1[110],s2[110];const LL M=1000000000+9;void init(){    c[0][0]=1;    for (int i=1;i<110;i++){        c[i][0]=1;        for (int j=1;j<=i;j++){            c[i][j]=c[i-1][j-1]+c[i-1][j];            c[i][j]%=M;        }    }}int main(){    init();    while (scanf("%d%d%d",&n,&k,&m)!=EOF)    {        scanf("%s%s",s1,s2);        int a=0;        for (int i=0;i<n;i++){            if (s1[i]!=s2[i]){                a++;            }        }        memset(dp,0,sizeof dp);        dp[0][a]=1;        for (int i=0;i<k;i++){            for (int j=0;j<=n;j++){                if (dp[i][j]){                    for (int q=0;q<=min(m,j);q++){                        int sta=j+m-2*q;                        dp[i+1][sta]+=c[j][q]*c[n-j][m-q]%M*dp[i][j]%M;                        if (dp[i+1][sta]>=M) dp[i+1][sta]%=M;                    }                }            }        }        printf("%lld\n",dp[k][0]);    }    return 0;}

 


联系
我们