这题当M=N=0的时候要输出1.000 刚写的时候默认从第二次开始取了.
详见代码:
#include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> #include <iostream> using namespace std; /* 题意:从一个拥有无限多的盒子中拿出不同颜色的糖果,拿出任何一种颜色的概率都是1/C 每次拿出来的糖果都放在桌子上,如果有相同颜色的糖果,就把这两颗糖果吃掉.问 拿了N次后,桌子上面剩余的糖果数量为M的概率是多大 解法:设状态dp[i][j]为选i次后剩余j颗糖果的概率为多大,省略了一维糖果的颜色数,因此 每次需要重新计算这个dp值,有如下dp方程: dp[i][j] = dp[i-1][j-1] * (C-j+1)/C + dp[i-1][j+1] * (j+1)/C 含义就是从上一次后拿到了一颗不同颜色的糖果,桌子上增加了一颗糖果而来 或者是拿到了一颗相同颜色的糖果,桌子上减少了一颗糖果而来 通过牛人的测试,当N大于1000的时候,为偶数就当做1000处理,为奇数的时候就当做 1001处理,因为N很大之后,仅仅靠小数点的后三位已经反映不去其差别 */ int C, M, N; double dp[2][1005][105]; void DP() { memset(dp, 0, sizeof (dp)); dp[1][1][1] = 1.0; // 摸一次一定会得到一个颜色的糖果 for (int i = 2; i <= N; ++i) { int x = i & 1; for (int j = 0; j <= C; ++j) { if (j - 1 >= 0) dp[x][i][j] += dp[!x][i-1][j-1]*(C-j+1)/C; if (j + 1 <= C) dp[x][i][j] += dp[!x][i-1][j+1]*(j+1)/C; } } } int main() { while (scanf("%d", &C), C) { scanf("%d %d", &N, &M); if (N == 0 && M == 0) { printf("%.3lf\n", 1.); continue; } if ((N&1)^(M&1) || M > C || M > N) { printf("%.3lf\n", 0.); continue; } if (N > 1000) { N = N & 1 ? 1001 : 1000; } DP(); printf("%.3lf\n", dp[N&1][N][M]); } return 0; }