题形：概率DP
题意：有n个物品，和得到每个物品的概率。问收集齐所有物品的期望次数。
思路：
面对一个局面，我们都考虑 拿一次 以后 会怎么样？
对于一个物品：E = p*1 + (1-p)*(1+E);
期望 我这一次拿到了 我这一次没拿到，还需要拿(1+E)次 （这里的1 代表这次， E表示以后还要拿E次）
对于两个物品：E__ = p1*(1+E1_) + p2*(1+E_2) + (1-p1-p2)*(1+E__)
解释第一项：我这次拿到了1,那到1以后我还需要拿 E1_ 次，所以 p1 的概率 我需要拿 1+E1_次
额。。看不懂继续百度吧。
然后这里用状态压缩DP完成
坑点： 递归超时，递推OK。
代码：
#include <cstdio> #include <cstring> double p[30]; double dp[(1<<21)]; //bool vis[(1<<21)]; int n; //double dfs(int now) { // //printf("n = %d, now = %d ", n, now); // if (vis[now]) { // //printf("dp[now] = %lf ", dp[now]); // return dp[now]; // } // double ans = 0; // double sump = 0; // for (int i = 0; i < n; i++) { // if ((now&(1<<i))==0) { // //printf("i = %d, p[i] = %lf ", i, p[i]); // ans += p[i]*(1+dfs((now|(1<<i)))); // sump += p[i]; // } // } // ans += (1-sump); // vis[now] = true; // return dp[now] = ans/sump; //} int main() { while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) { scanf("%lf", &p[i]); } //memset(vis, false, sizeof(vis)); //vis[((1<<n)-1)] = true; dp[((1<<n)-1)] = 0; for (int i = ((1<<n)-1)-1; i >= 0; i--) { double ans = 0; double sump = 0; for (int j = 0; j < n; j++) { if ((i&(1<<j)) == 0) { ans += p[j]*(1+dp[(i|(1<<j))]); sump += p[j]; } } ans += (1-sump); dp[i] = ans/sump; } //printf("%lf ", dfs(0)); printf("%lf ", dp[0]); } return 0; }