ZOJ - 4114 Flipping Game

　　题目大意：给出两个串s,t，n个灯泡的序列，1代表开着，0代表关着，一共操作k轮，每轮改变m个灯泡的状态，问最终能把s串变成t串的方案数。

　　很奇特的一种dp，首先状态的定义dp[i][j]是前i轮操作后，有j个灯泡的状态跟最终串不一样的方案数。这样初始化是dp[0][num]=1其他全0，num是s串和t串状态不同的灯泡数目。然后状态的转移，对于每一轮我们枚举有j个灯泡跟最终串状态不一样，然后再枚举上一轮有kk个灯泡与最终串状态不一样，每次操作都会改变灯泡的状态，设上一轮不一样的状态改变了x个，一样的状态改变了y个，那么x,y应该有0<=x<=kk,0<=y<=n-kk，x+y=m,kk-x+y=j,这四个约束条件，而满足约束条件的就是合法的转移过程，也就是dp[i][j]=dp[i-1][kk]*C[kk][x]*C[n-kk][y]，最后注意取模。

 #include<cstdio>

 typedef long long ll;

 const int N=,mod=;

 ll dp[N][N],C[N][N];

 char a[N],b[N];

 void getC()

 {

     C[][]=1ll;

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

     {

         C[i][]=1ll;

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

         {

             if(j<=i/)

                 C[i][j]=C[i-][j]+C[i-][j-];

             else

                 C[i][j]=C[i][i-j];

             if(C[i][j]>=mod)

                 C[i][j]%=mod;

         }

     }

 }

 void init(int n,int k)

 {

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

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

             dp[i][j]=0ll;

     int num=;

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

         num+=(a[i]!=b[i]);

     dp[][num]=;

 }

 int main()

 {

     int t,n,m,k,x,y;

     getC();

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d%d",&n,&k,&m);

         scanf("%s%s",a,b);

         init(n,k);

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

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

                 for(int kk=((m+j)&);kk<=m+j&&kk<=n;kk+=)

                 {//把约束条件联立一下可以得出合法条件下的x,y

                     y=(m+j-kk)/;

                     x=m-y;

                     if(x<||y<||x>kk||y>n-kk)

                         continue;

                     dp[i][j]+=dp[i-][kk]*C[kk][x]%mod*C[n-kk][y]%mod;

                     if(dp[i][j]>=mod)

                         dp[i][j]%=mod;

                 }

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

     }

     return ;

 }

神奇的dp

巴特西

ZOJ - 4114 Flipping Game

最新文章

热门文章