POJ1322Chocolate--概论DP

每次从包装中取出一块巧克力并放在桌子上。如果桌子上有两个相同颜色的巧克力，则将这两个丢掉。
如果包中有C种颜色的巧克力（颜色均匀分布），从包装中取出N个巧克力后，桌子上确实有M个巧克力的概率是多少？

对于每种情况，存在三个非负整数：C（C <= 100），N和M（N，M <= 1000000）。

题目要求取出n个巧克力后，桌上剩余m个巧克力的概率。那我们就按着题目意思来，dp[i][j]的含义就是这个

首先，判断边界条件，如果取出0个巧克力，那么桌子上剩余0个巧克力的概率是多少？？？很简单，dp[0][0] = 1;

另外，针对输入的c，n，m进行非法判断，即概率为0.000的直接输出就好了

m的个数是小于等于c的，因为如果某种颜色的巧克力数量是大于等于2的，那么一定是两个都被拿走了，也就是最后剩下的每种巧克力要么只有一个要么没有。所以最多所有的颜色都在桌上，都是一个。

dp[i][j]表示前i次操作(即取出i个巧克力)后，桌上出现j个巧克力的概率。试想，如果i+j是奇数会是什么情况？

dp[i][j]是等于0的(不可能出现的情况)。为什么不可能出现呢，因为每次取出的球都会现放到桌上比较，如果没有重复的颜色，则桌子上球数+1,如果有重复，将重复的两个球都拿掉，也就是i的次数首先加到m上，此刻的m要么不变，要么-2,不会出现奇数的情况。所以dp[i][j]中i+j为奇数则概率是0

可以手动模拟验算下。

那么，状态转移方程怎么来呢？？因为要么取到的球和桌子上球的颜色不重复，即 dp[i-1][j-1] * (c-j+1.0)/c; 就是在前面拿出i-1个巧克力后，桌子剩余j-1个巧克力的概率上，乘上这次取出的巧克力与桌子上巧克力颜色不重复的概率，c-j+1.0,表示颜色总数减去桌上的不同颜色的，剩余的也是不同颜色的，再除以c就是对应的取出不同颜色的概率了。

要么取出的球和桌上某个球的颜色相同，要一起拿走，方程是这样：dp[i-1][j+1]*（j+1.0)/c ，j+1/c，即取出的球的颜色和桌上的球的某个颜色相同了

dp[i][j]将二者加起来即可

另外，在对很大的n进行计算时，可以将其看成一个较小的n，因为很大的n对应的概率和较小的数m的概率只有小数点后好几位才会不同，所以可以转换下

 1 #include <cstdio>

 #include <iostream>

 #include <cstring>

 using namespace std;

 #define MAX 105

 int main()

 {

     int c = , n = , m = ;

     double dp[MAX * ][MAX];

     while (scanf("%d", &c) != EOF)

     {

         if (c == )

         {

             break;

         }

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

         if (m > c || m > n || (m + n) %  != )//特判

         {

             printf("0.000\n");

             continue;

         }

         memset(dp, , sizeof(dp));

         if (n > )//将较大的n转换较小的

         {

             n =  + n % ;//奇偶选择

         }

         dp[][] = ;

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

         {

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

             {

                 if ((i + j) %  != )

                 {

                     continue;

                 }

                 dp[i][j] = dp[i - ][j - ] * (c - j + 1.0) / c + dp[i - ][j + ] * (j + 1.0) / c;

             }

         }

         printf("%.3lf\n", dp[n][m]);

     }

     return ;

 }

巴特西

POJ1322Chocolate--概论DP

最新文章

热门文章