hdu 4336 Card Collector (容斥 or dp)

hdu 4336 Card Collector (容斥 or dp)

题目：​​现在求出收集完所有卡片需要袋子数目的期望。

分析：最开始自己用容斥做的，从简单的情况入手，

保证收集到卡片1——p1 对应次数：1p1

保证收集到卡片2——p2 对应次数：1p2

保证收集到卡片1或者卡片2——p1+p2 对应次数：1p1+p2

把这两张卡片统统收集到——交集部分的概率，对应次数：1p1+1p2−1p1+p2

奇加偶减，容斥。

code:

#include #include using namespace std;double f[25];int main(){ int n; while(cin>>n){ for(int i=0;i

但是不会概率dp毕竟是不足，以学习的心态开始了第二种做法：

期望=∑piwi (概率*权重的和）

收集到x张卡片的期望：E(x)=∑p(xd)[1+E(y)]+[1−∑p(xd)](1+E(x))

即在y状态下能收集到+不能收集到

经过化简：E(x)=∑p(xd)E(y)+1∑p(xd)

解释xd: 表示第d个元素被收集到，以二进制看待整个过程，求期望一般是从高位推到低位，即从11⋯1 推到00⋯0 出现0的地方就出现交集，

code:

#include #include #include using namespace std;double dp[(1<<20)+10],p[25];int main(){ int n; while(cin>>n){ for(int i=0;i=0;i--){ // start at (1<

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