首页 > 代码库 > hdu-4336-Card Collector-概率DP
hdu-4336-Card Collector-概率DP
以后还是使用递推把,不能用记忆化了,记忆化太耗时间了。。。
因为N很小,所以我们可以用状态压缩。用压缩起来的状态表示已经拥有的卡片。
然后根据状态之间的关系进行求解。
#include <iostream> #include<stdio.h> #include<string.h> #include<math.h> using namespace std; #define maxn 110000 #define eps 1e-6 #define zero(x) (fabs(x)<0?0:x) double dp[1<<21]; double p[23]; int n; int main() { double x,y; while(~scanf("%d",&n)) { double p0=1; for(int i=1;i<=n;i++) { scanf("%lf",&p[i]); p0-=p[i]; } p[0]=p0; dp[0]=0; for(int i=1;i<(1<<n);i++) { x=p[0]; dp[i]=1.0; for(int j=0;j<n;j++) { if(i&(1<<j))dp[i]+=p[j+1]*dp[i-(1<<j)]; else x+=p[j+1]; } dp[i]=dp[i]/(1-x); } printf("%.5f\n",dp[(1<<n)-1]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。