首页 > 代码库 > hdoj 4336 Card Collector 【概率dp】

hdoj 4336 Card Collector 【概率dp】

题目:hdoj 4336 Card Collector 


题意:集齐卡片抽大奖,每个卡片概率,及其卡片个数,然后问你及其卡片要买卡片数量的期望。


分析:最多20张卡片,用状态压缩来表示是否拿了某个卡片。

比如现在有状态10010,表示拿了第2 3 5的状态下的期望。

我们要求它,我们可以先得到11010,10110,10011,的期望,然后乘以各自位没拿的概率就是总的期望。在除去总概率就是当前的期望,

不是很懂啊///数学智商有点捉急


AC代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 22;
double dp[1<<N],p[N];  //dp[st] 表示状态st下拿为0状态的卡片的期望
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        double sum=0;
        for(int i=0;i<n;i++)
            scanf("%lf",&p[i]);
        dp[(1<<n)-1]=0;
        for(int st=(1<<n)-2;st>=0;st--)
        {
            double tt=0;
            for(int i=0;i<n;i++)
            {
                if(!(st&(1<<i)))
                    dp[st]+=(dp[st|(1<<i)])*p[i],tt+=p[i];
            }
            dp[st]/=tt;
        }
        printf("%.5lf\n",dp[0]);
    }
    return 0;
}


hdoj 4336 Card Collector 【概率dp】