UVa 12063 (DP) Zeros and Ones

题意：

找出长度为n、0和1个数相等、没有前导0且为k的倍数的二进制数的个数。

分析：

这道题要用动态规划来做。

设dp(zeros, ones, mod)为有zeros个0，ones个1，除以k的余数为mod的二进制数的个数，则状态转移方程为：

dp(zeros + 1, ones, (mod>>1) % k) += dp(zeros, ones, mod)

dp(zeros, ones + 1, ((mod>>1)+1) % k) += dp(zeros, ones, mod)

分别用记忆化搜索和递推的方式写了一遍，递推要比记忆化搜索快一半的时间。

 #include <cstdio>

 #include <cstring>

 int n, k;

 long long d[][][];

 long long dp(int zeros, int ones, int mod)

 {

     if(zeros + ones > n || zeros > n/ || ones > n/) return ;

     if(d[zeros][ones][mod] != -) return d[zeros][ones][mod];

     return d[zeros][ones][mod] = dp(zeros+, ones, (mod<<)%k) + dp(zeros, ones+, (((mod<<)%k)+)%k);

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     for(int kase = ; kase <= T; ++kase)

     {

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

         if(n %  ==  || k == ) { printf("Case %d: 0\n", kase); continue; }

         memset(d, -, sizeof(d));

         d[n/][n/][] = ;

         printf("Case %d: %lld\n", kase, dp(, , ));

     }

     return ;

 }

记忆化搜索

 #include <cstdio>

 #include <cstring>

 int n, k;

 long long dp[][][];

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     for(int kase = ; kase <= T; ++kase)

     {

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

         if(n %  ==  || k == ) { printf("Case %d: 0\n", kase); continue; }

         n /= ;

         memset(dp, , sizeof(dp));

         dp[][][%k] = ;

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

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

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

                 {

                     dp[i+][j][(m<<)%k] += dp[i][j][m];

                     dp[i][j+][((m<<)+)%k] += dp[i][j][m];

                 }

         printf("Case %d: %lld\n", kase, dp[n][n][]);

     }

     return ;

 }

递推

巴特西

UVa 12063 (DP) Zeros and Ones

最新文章

热门文章