首页 > 代码库 > 11181-Probability
11181-Probability
不得不说这道题十分猥琐啊,递归求解,我RE了接近20次,最后发现还是数组开小了。
#include<stdio.h> #include<iostream> #include<math.h> #include<vector> #include<string.h> using namespace std; int biao[250000],n,r,zhi = 0; double p[250000],possi[250000]; int v[250000][25]; void dfs(int cur,int buy) { if(cur == n) { if(buy != r) return; possi[zhi] = 1; for(int i = 0;i < n;i++) { if(biao[i]) v[zhi][i] = 1; else v[zhi][i] = 0; } for(int i = 0;i < n;i++) { if(biao[i]) possi[zhi] *= p[i]; else possi[zhi] *= (1 - p[i]); } zhi++; return; } biao[cur] = 1; //买 dfs(cur + 1,buy + 1); biao[cur] = 0; //不买 dfs(cur + 1,buy); } int main() { // freopen("out.txt","w",stdout); int kase = 0; while(cin>>n>>r) { if(!n && !r) break; printf("Case %d:\n",++kase); memset(v,0,sizeof(v)); memset(p,0,sizeof(p)); memset(possi,1,sizeof(possi)); memset(biao,0,sizeof(biao)); for(int i = 0;i < n;i++) cin>>p[i]; dfs(0,0); double fenmu = 0; for(int i = 0;i < zhi;i++) fenmu += possi[i]; for(int i = 1;i <= n;i++) //看看哪个容器里有i,把i买了的概率求出来 { double fenzi = 0; for(int j = 0;j < zhi;j++) { double temp = 1;int flag =0; if(v[j][i - 1]) //这种情况i买了 { flag = 1; for(int k = 0;k < n;k++) { if(v[j][k]) temp *= p[k]; else temp *= (1 - p[k]); } } if(flag) fenzi += temp; } printf("%.6lf\n",(double)fenzi*1.0/fenmu); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。