题意:买一包小吃,会附带最多一张卡片,注意可以没有,给你卡片出现的概率,问你取完所有卡片所需要买的小吃包数。
由于无后续性,可以直接递归做。
代码:
#include<iostream> #include<vector> #include<string> #include<queue> #include<map> #include<cstdio> #include<cstring> #define maxn 1<<20 #define INF 0xfffffff #define min(a,b) a<b?a:b #define max(a,b) a>b?a:b using namespace std; int n; double dp[maxn],a[maxn]; double DP() { double p,sum; memset(dp,0,sizeof(dp)); dp[(1<<n)-1]=0;//表示取了哪些,所有都取了则为0 for(int i=((1<<n)-2);i>=0;i--) { p=0; sum=1; for(int j=0;j<n;j++) { if((i&(1<<j))==0)//有哪一个没取 { p+=a[j]; sum=sum+dp[i|(1<<j)]*a[j]; } } dp[i]=sum/p; } return dp[0]; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { scanf("%lf",&a[i]); //sump+=a[i]; } printf("%.5lf\n",DP()); } return 0; }