csu1290 Random Integers ——DP入门题&&比赛残留题

题目链接：http://122.207.68.93/OnlineJudge/problem.php?id=1290

题目大意：

　　从K个不同的数字里面有放回地随机选N次，求选到的不同的数字的种类的期望。

题目思路：

　　这题不能用概率公式推导。因为有很多项的阶乘，应该会超double范围。应该用DP做。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 const int MAX=1000+10;
 7 double dp[MAX][MAX];
 8 int main(void) {
 9   int i, j, k, t; 
10   double N, K;
11   scanf("%d", &t);
12   while (t--) {
13     scanf("%lf%lf", &K, &N);
14     double sum = 0.0;
15     for (i = 0; i <= N; ++i) for (j = 0; j <= K; ++j)
16       dp[i][j] = 0.0;
17     dp[0][0] = 1.0; 
18     for (i = 1; i <= N; ++i){
19       for (j = 1; j <= K; ++j){
20         dp[i][j]=dp[i-1][j-1]*(K-j+1)/K + dp[i-1][j]*(j/K);
21         //sum += (j*dp[i][j]);
22       }
23     }
24     for (i = 1; i <= K; ++i) {
25       sum += (i * dp[(int)N][i]);
26     }
27     printf("%.5f\n", sum);
28   }
29 
30   return 0;
31 }

这比赛输这么惨也不是什么意外……

努力练吧，呵呵。