hdu 4336 Card Collector[期望]

Sample Input

 1
0.1
2
0.1 0.4 

思路：状态压缩，从后往前推；

f [ s ]=1+f [ s ]*(1-segma[p. i ] ) + f[s]*segma[p. j ] + f[s|1<<k ]*segma[p.k] ;

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#define INF 0x7fffffff
#define SUP 0x80000000
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long LL;
const int N=100007;

double a[30],dp[5000000];
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        double tt=0,sum;
        for(int i=0;i<n;i++)
        {
            scanf("%lf",a+i);
            tt+=a[i];
        }
        tt=1-tt;   //空包的概率
        dp[(1<<n)-1]=0;
        for(int i=(1<<n)-1-1;i>=0;i--)
        {
            dp[i]=1;
            sum=0;
            for(int j=0;j<n;j++)
            {
                if(i&1<<j) sum+=a[j];
                else dp[i]+=dp[i|1<<j]*a[j];
            }
            dp[i]/=1-tt-sum;
        }
        printf("%.4f\n",dp[0]);
    }
    return 0;
}

hdu 4336 Card Collector[期望]

原文：http://blog.csdn.net/code_or_code/article/details/44617397