题目地址:https://vjudge.net/problem/SGU-495#author=0

题意


把N个奖品分给M个人,最初N个奖品被装到了N个盒子,每个盒子都独立放在一个房间里,M个人依次选择一个盒子,如果盒子内有奖品则把奖品取走,不管有无奖品都要把盒子再放回原处。

求被拿走的奖品数的期望值

 

解题思路


dp[i]表示第i个人选择时对应的被拿走奖品数的期望值。

dp[1]=1;对于第i个人(i>=2),有选到有礼物的盒子和选到无礼物的盒子两种情况

  

令t=(n-1)/n

化简可知dp[m]=1+t^1+t^2+..+t^m-1

精度的话输出%.101lf就行

 

ac代码


VJ上面这道题不能提交,但是思路基本上时正确的吧。欢迎指错

#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 1005
typedef long long ll;
using namespace std;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int n,m;//m个人
    cin>>n>>m;
    double t=(n-1)*1.0/n,ans=1;
    for(int i=1;i<m;i++)
        ans+=pow(t,i);
    printf("%.101lf\n",ans);
    return 0;
}