SGU 495 Kids and Prizes 概率DP 或 数学推理

题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=495

有n个箱子 m个人

有两个思考的角度

1.从箱子的角度

对于一个箱子来说 不被选中的概率是((n-1)/n)^m 所以被选中的概率是（1 - ((n-1)/n)^m）

箱子之间是互相独立的

所以总期望是：n * （1 - ((n-1)/n)^m）

【我是算样例然后无意中发现的规律 再证明】

2.从人的角度

从题目中看 人是one by one进去选的 所以可以看作有先后顺序 考虑动态规划

dp[i]表示第i个人选到礼物的概率

两种情况：

a.若第i-1个人没有选到 那么第i个人获得礼物的概率跟第i-1个人一样 因为礼物数没有减少 则有(1 - dp[i-1]) * dp[i-1]

b.若第i-1个人有选到 那么礼物数减少了1 所以获得礼物的概率就减少了1/n 则有dp[i-1] * (dp[i-1] - 1/n)

综上 有dp[i] = (1 - dp[i-1]) * dp[i-1] + dp[i-1] * (dp[i-1] - 1/n);

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <set>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    //freopen("in.txt", "r", stdin);

    double n, m;

    scanf("%lf%lf", &n, &m);

    printf("%.9f
", n * (1 - pow((n-1)/n, m) ));

    return 0;
}

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <set>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 100010;
double dp[maxn];

int main()
{
    //freopen("in.txt", "r", stdin);

    int n, m;

    scanf("%d%d", &n, &m);

    dp[1] = 1;

    for(int i = 2; i <= m; i++)
    {
        dp[i] = dp[i-1]*(dp[i-1] - 1.0/n) + (1 - dp[i-1])*dp[i-1];
    }

    double ans = 0;
    for(int i = 1; i <= m; i++)
        ans += dp[i];

    printf("%.9f
", ans);

    return 0;
}