设为首页 加入收藏

TOP

poj 2151 Check the difficulty of problems (概率dp)
2015-07-20 17:29:31 来源: 作者: 【 】 浏览:2
Tags:poj 2151 Check the difficulty problems 概率
/*
一次比赛中,共M道题,T个队,p[i][j]表示队i解出题j的概率;问每队至少解出一题且冠军队至少解出N道题的概率。
dp[i][j][k]表示第i支队伍在前j道题中解出k道的概率


问题的解可以转化为:每队均至少做一题的概率(用P1表示)减去每队做题数均在1到N-1
之间的概率(用P2表示)。
*/
# include 
  
   
# include 
   
     # include 
    
      # include 
     
       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; } 
     
    
   
  

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇HDU 1565 方格取数(1)(状压dp) 下一篇BZOJ 2097 Exercise 奶牛健美操 ..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·About - Redis (2025-12-26 08:20:56)
·Redis: A Comprehens (2025-12-26 08:20:53)
·Redis - The Real-ti (2025-12-26 08:20:50)
·Bash 脚本教程——Li (2025-12-26 07:53:35)
·实战篇!Linux shell (2025-12-26 07:53:32)