SGU 495 Kids and Prizes

题意：给n个盒子，每个盒子里有一个礼物。有m个人，每个人拿起一个盒子，如果里面有礼物则将礼物取出并带走，无论里面有没有礼物都将盒子留下。问这m个人带走礼物数量的期望。

解法：设d[i]表示第i个人拿盒子以后，总共带走的礼物数量的期望。d[i] = (d[i-1] + 1)* (n-d[i-1]) / n + d[i-1] * d[i-1] / n。复杂度O(m)。

　　　虽然解法写着很简单，但是做多了概率dp的题以后，我一来就用了别的方法来设置数组，弄了半天才做出来。

tag:math, 概率dp

/*
 * Author:  Plumrain
 * Created Time:  2013-11-12 18:35
 * File Name: DP-SGU-495.cpp
 */
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n, m;
    while (scanf ("%d%d", &n, &m) != EOF){
        double x[2] = {1.0};
        for (int i = 2; i <= m; ++ i){
            x[1] = (x[0] + 1) * (n - x[0]) / n + x[0] * x[0] / n;
            x[0] = x[1];
        }
        if (m > 1)
            printf ("%.10f
", x[1]);
        else
            printf ("%.10f
", m ? 1.0 : 0.0 );
    }
    return 0;
}