SP1026 FAVDICE

题目描述

一个(n(n leq 1000))面的骰子，求期望掷几次能使得每一面都被掷到。

输入输出样例

输入样例#1：

2
1
12

输出样例#1：

1.00
37.24

思路：期望(dp)中典型的赠券收集问题，用f[i]表示还剩i个面没有掷到，那么掷到之前没有掷到过的面的概率为((n-i)/n)，然后次数的期望值就是概率分之一，然后进行逆向(dp)即可。

代码：

#include<cstdio>
#define dl double
dl f[1007];
int n,t;
int main() {
  scanf("%d",&t);
  while(t--) {
    scanf("%d",&n);
    f[n]=0;
    for(int i=n-1;i>=0;--i) 
      f[i]=f[i+1]+(n/(n-(double)i));
    printf("%0.2lf
",f[0]);
  }
  return 0;
}