Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3001 Accepted Submission(s): 1435
Special Judge
求期望
方法一：状压
1.逆序枚举所有状态 d[i] 表示状态为i时收集完所有卡片的期望步数。
d[i] = 1 + ∑(d[i | (1 << j)] * p[j])(ps: 累加所有走一步会增加新一张卡片的期望步数) + (1 - t) * d[i](ps: t为增加一张新卡片的概率);
#include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <algorithm> using namespace std; #define ll long long #define _cle(m, a) memset(m, a, sizeof(m)) #define repu(i, a, b) for(int i = a; i < b; i++) #define MAXN (1 << 20) double d[MAXN + 1]; double p[25]; int main() { int n; while(~scanf("%d", &n)) { memset(d, 0, sizeof(d)); repu(i, 0, n) scanf("%lf", &p[i]); if((1 << n) - 1) d[(1 << n) - 1] = 0.0; double t; for(int i = (1 << n) - 2; i >= 0; i--) { d[i] += 1.0; t = 0.0; for(int j = 0; j < n; j++) if(!(i & (1 << j))) { d[i] += p[j] * d[i | (1 << j)]; t += p[j]; } d[i] /= t; } printf("%.4lf\n", d[0]); } return 0; }
原文：http://www.cnblogs.com/sunus/p/4445187.html
