lightoj 1248 Dice (III) 期望 DP

dp[i]表示一共n面，已经看见i面，需要多少次看完所有面的期望。

dp[n] = 0。

dp[i] = i / n * dp[i] + (n - i) / n * dp[i + 1] + 1移项处理下就行了。

dp[i] = dp[i + 1] + n / (n - i)

#include <cstdio>
#include <algorithm>
using namespace std;
int T,cas,n;
double dp[100010];
int main()
{
    for (scanf("%d",&T);T != 0;T--)
    {
        scanf("%d",&n);
        dp[n] = 0;
        for (int i = n - 1;i >= 0;i--)
        {
            dp[i] = dp[i + 1] + (double)n / (n - i);
        }
        printf("Case %d: %.6lf
",++cas,dp[0]);
    }
    return 0;
}