首页 > 代码库 > poj 2151 Check the difficulty of problems (概率dp)
poj 2151 Check the difficulty of problems (概率dp)
/* 一次比赛中,共M道题,T个队,p[i][j]表示队i解出题j的概率;问每队至少解出一题且冠军队至少解出N道题的概率。 dp[i][j][k]表示第i支队伍在前j道题中解出k道的概率 问题的解可以转化为:每队均至少做一题的概率(用P1表示)减去每队做题数均在1到N-1 之间的概率(用P2表示)。 */ # include <stdio.h> # include <algorithm> # include <string.h> # include <iostream> using namespace std; double dp[1010][35][35]; double p[1010][35]; int main() { int i,j,k,n,t,m; while(~scanf("%d%d%d",&m,&t,&n),m+t+n) { for(i=1; i<=t; i++) { for(j=1; j<=m; j++) scanf("%lf",&p[i][j]); } memset(dp,0,sizeof(dp)); for(i=1; i<=t; i++) { dp[i][0][0]=1; for(j=1; j<=m; j++) { dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]); for(k=1; k<=m; k++) { dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]); } } } double p1=1,p2=1; for(i=1;i<=t;i++)///每队至少做一题的概率 p1*=1-dp[i][m][0]; double sum=0; for(i=1;i<=t;i++)///每队做题数均在1到N-1之间的概率 { sum=0; for(j=1;j<=n-1;j++)///单独一支队伍,同支队伍是用+ sum+=dp[i][m][j]; p2*=sum; } printf("%.3lf\n",p1-p2); } return 0; }
poj 2151 Check the difficulty of problems (概率dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。