Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u
cid=60444#status//K/0" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="display:inline-block; position:relative; padding:0px; margin-right:0.1em; vertical-align:middle; overflow:visible; text-decoration:none; font-family:Verdana,Arial,sans-serif; font-size:1em; border:1px solid rgb(211,211,211); color:rgb(85,85,85)">Status
Practicepid=4336" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="display:inline-block; position:relative; padding:0px; margin-right:0.1em; vertical-align:middle; overflow:visible; text-decoration:none; font-family:Verdana,Arial,sans-serif; font-size:1em; border:1px solid rgb(211,211,211); color:rgb(85,85,85)">HDU
4336
System Crawler (2014-10-23)
Description
As a smart boy, you notice that to win the award, you must buy much more snacks than it seems to be. To convince your friends not to waste money any more, you should find the expected number of snacks one should buy to collect a full suit of cards.
Input
of each card to appear in a bag of snacks.
Note there is at most one card in a bag of snacks. And it is possible that there is nothing in the bag.
Output
You will get accepted if the difference between your answer and the standard answer is no more that 10^-4.
Sample Input
1
0.1
2
0.1 0.4
Sample Output
10.000
10.500
/*************************************************************************
> File Name: t.cpp
> Author: acvcla
> Mail: acvcla@gmail.com
> Created Time: 2014年10月21日 星期二 21时33分55秒
************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
double dp[1<<20],p[1<<20],A[200];
void Init(int n){
memset(p,0,sizeof p);
memset(dp,0,sizeof dp);
for(int i=(1<<n)-1;i>0;i--){
double t=0;
for(int j=0;j<n;j++)if(1<<j&i)
{
p[i]+=A[j];
}
}
}
int n;
int main(int argc, char const *argv[])
{
while(~scanf("%d",&n)){
double s=1;
for(int i=0;i<n;i++){
scanf("%lf",A+i);
s-=A[i];
}
Init(n);
for(int i=(1<<n)-2;i>=0;i--){
double t=0;
double pi=p[i]+s;
for(int j=0;j<n;j++){
if((1<<j)&i)continue;
else{
int temp=i|(1<<j);
t+=dp[temp]*A[j];
}
}
dp[i]=(t+1)/(1-pi);
}
printf("%.4f\n",dp[0]);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。