Aimee

转态转移非常好想

状态压缩一下。然后倒着转移

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
double dp[1<<21];
int n;
double p[21];
double fai=1;
int main(){
    while(~scanf("%d",&n)){
        fai=1;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i){
            scanf("%lf",&p[i]);
            fai-=p[i];
        }
        for(int i=(1<<n)-2;i>=0;--i){
            double x=0;
            double y=fai;
            for(int j=1;j<=n;++j){
                if((i&(1<<(j-1)))){
                    y+=p[j];
                }else{

                    x+=p[j]*(1+dp[i|(1<<(j-1))]);
                }
            }
            dp[i]=(x+y)/(1-y);
        }
        printf("%.4lfn",dp[0]);
    }
    return 0;
}