hdu 4336

小吃包装袋里面有随机赠送一些有趣的卡片，如今你想收集齐 N 张卡片。每张卡片在食品包装袋里出现的概率是p[i] ( Σp[i] <= 1 ), 问你收集全部卡片所需购买的食品数量的期望是多少。

对于每袋食品。有两种结果，该卡片已经收集到了和没有收集到(没有卡片的情况视为收集到了)。

把已经收集到的卡片的集合记为 s ，dp[s] 表示已经收集到集合s的卡片情况下收集齐全部的卡片的购买数量的期望，s 为空集即为所求。s  为全集时dp[s] = 0;

对于上面说的两种情况 _si 表示集合 s 加入一个不在 s 中的卡片 i 的集合 Σ((dp[_si] + 1) * p[i]) ,而抽到已经收集到的卡片则是dp[s];

dp[s] = Σ((dp[_si] + 1) * p[i]) + dp[s] * (1 - Σ(p[i]));

而集合s我们能够用二进制非常好解决。

/***********************************************

 ** problem ID	: poj_2096.cpp

 ** create time	: Sat Jul 25 13:21:58 2015

 ** auther name	: xuelanghu

 ** auther blog	: blog.csdn.net/xuelanghu407

 **********************************************/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, s;

double dp[1010][1010];

void init() {

	for (int i=0; i<=n; i++) {

		for (int j=0; j<=s; j++) {

			dp[i][j] = -1.0;

		}

	}

}

double DP(int i, int j) {

	if (dp[i][j] != -1.0) return dp[i][j];

	if (i == n && j == s) return dp[i][j] = 0.0;

	double res = 1.0;

	if (i+1 <= n && j+1 <= s)

		res += DP(i+1, j+1) * (n - i) * (s - j) * 1.0 / (n * s);

	if (i+1 <= n)

		res += DP(i+1, j) * (n-i) * j * 1.0 / (n * s);

	if (j+1 <= s)

		res += DP(i, j+1) * i * (s - j) * 1.0 / (n * s);

	return dp[i][j] = res / (1.0 - (i * j) * 1.0  / (n * s));

}

int main () {

	while (cin >> n >> s) {

		init();

		printf ("%.4lf\n", DP(0, 0));

	}

	return 0;

}