HDU 4336 Card Collector——状压+期望dp

HDU 4336 Card Collector——状压+期望dp

题意： 有N(1<=N<=20)张卡片，每包中含有这些卡片的概率为p1,p2,````pN. 每包至多一张卡片，可能没有卡片。

求需要买多少包才能拿到所以的N张卡片，求次数的期望。

思路：

状压思路很好想，注意推出状态转移方程后注意移项（可能要移多项）

#include #include #include #include #include using namespace std;const double eps = 1e-4;int n;double p[25], dp[1<<20];int main() { while (~scanf("%d", &n)) { p[0] = 1; for (int i = 1; i <= n; i++) { scanf("%lf", &p[i]); p[0] -= p[i]; } if (fabs(1-p[0]) < eps) { printf("%.4f\n", 0); continue; } memset(dp, 0, sizeof(dp)); for (int s = (1<= 0; s--) { double x = 0; for (int i = 1; i <= n; i++) { if (s & (1<<(i-1))) continue; x += p[i]*dp[s|(1<<(i-1))]; } double y = p[0]; for (int i = 1; i <= n; i++) if (s & (1<<(i-1))) y += p[i]; dp[s] = (x + 1)/(1 - y); } printf("%.4f\n", dp[0]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。