hdu 4336 Card Collector (概率dp)

题目大意：

收集卡片，问收集齐n张卡片需要买多少包方便面的期望- -虽然不是方便面。

解题思路：

用1表示该位的卡片已经有，0表示没有。

dp[s] 表示拥有了s状态下1的卡片，还要买多少包才能凑齐n张卡片的期望。

所以 ，当你及其了所有的卡片。即 dp[(1<<n)-1]=0.0;

下面再来分析状态转移。

假设我们要收集齐 6 张，可是现在我们收集齐了五张。 那么你要中第六张。

就是第六包要中1 或2 或3 ...或6...

所以要枚举所有 五包的情况，然后因为任一种情况都是互不影响的，所以是相加。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

double p[25];
double dp[1<<21];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        scanf("%lf",&p[i]);

        int all=(1<<n)-1;

        dp[all]=0.0;

        for(int s=all-1;s>=0;s--)
        {
            dp[s]=1.0;
            double tmp=0;
            for(int j=0;j<n;j++)
            {
                if(!(s&(1<<j)))
                {
                    dp[s] += p[j] * dp[s|(1<<j)];
                    tmp+=p[j];
                }
            }
            dp[s]/=tmp;
        }
        printf("%lf\n",dp[0]);
    }
    return 0;
}

hdu 4336 Card Collector (概率dp)

原文：http://blog.csdn.net/u010709592/article/details/18952933