题意：n张卡片，每一次取一个盒子，盒子里装有卡片i的概率是p[i]，求得到所有卡片所需要开的盒子的期望数（n<=20）

#include 
     
      #include 
      
       using namespace std;const int N=22;int n;double p[N], f[1<
       
        =0; --s) {			double up=1, down=0;			for(int i=0; i
       
      
     

　　

设$f[s]$表示当前得到状态为$s$的卡片还需要开的盒子的期望数：

考虑开一个箱子：

1、没有卡片，概率为：$1-\sum_{i} p[i]$；期望和为：$(1-\sum_{i} p[i])f[s]$ 

2、卡片$i$已经收集过了，概率为：$p[i]$；期望和为：$\sum_{i \in s} p[i]f[s]$

3、卡片$i$没有收集过，概率为：$p[i]$；期望和为：$\sum_{i \notin s} p[i]f[s \cup \{ i \}]$

所以

$$

\begin{align}

f[s]

& = (1-\sum_{i} p[i])f[s] + \sum_{i \in s} p[i]f[s] + \sum_{i \notin s} p[i]f[s \cup \{ i \}] \\

& = \frac{1 + \sum_{i \notin s} p[i]f[s \cup \{ i \}]}{\sum_{i \notin s} p[i]}

\end{align}

$$

然后还有注意，spj的话精度一定要注意啊，不要只输出了几位= =，最好多输出几位，你懂的...于是就wa了几发..