首页 > 代码库 > poj 2151 Check the difficulty of problems(概率dp)
poj 2151 Check the difficulty of problems(概率dp)
http://poj.org/problem?id=2151
有t个队伍,m道题,给出每个队伍做出每道题的概率。求出每个队伍至少做出一道题并且冠军队伍至少做出n道题的概率。
只要设出数组来,就很直观了。
dp[i][j][k]表示第i个队伍在前j道题中解出k道题的概率,s[i][j]表示第i个队伍最多解出j道题的概率。
首先初始化dp[i][0][0]和dp[i][j][0],那么dp[i][j][k] = dp[i][j-1][k-1]*a[i][j] + dp[i][j-1][k]*(1-a[i][j])。
s[i][j] = dp[i][m][0] + dp[i][m][1] + .....+dp[i][m][j]。
首先求出每个队伍至少解出一道题的概率p1 = (1-s[1][0]) * (1-s[2][0]) *.....*(1-s[t][0])。
然后求出每个队伍都解除1~n-1道题的概率p2 = (s[1][n-1] - s[1][0]) * (s[2][n-1] - s[2][0])*......*(s[t][n-1] - s[t][0])。
那么答案就是p1-p2。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; int m,t,n; double dp[1010][35][35],s[1010][35]; double a[1010][35]; int main() { while(~scanf("%d %d %d",&m,&t,&n)) { if(m == 0 && t == 0 && n == 0) break; for(int i = 1; i <= t; i++) { for(int j = 1; j <= m; j++) scanf("%lf",&a[i][j]); } memset(dp,0,sizeof(dp)); for(int i = 1; i <= t; i++) { dp[i][0][0] = 1; for(int j = 1; j <= m; j++) { dp[i][j][0] = dp[i][j-1][0]*(1-a[i][j]); for(int k = 1; k <= j; k++) dp[i][j][k] = dp[i][j-1][k-1]*a[i][j] + dp[i][j-1][k]*(1-a[i][j]); } } memset(s,0,sizeof(s)); for(int i = 1; i <= t; i++) { for(int j = 0; j <= m; j++) { for(int k = 0; k <= j; k++) s[i][j] += dp[i][m][k]; } } double p1 = 1; for(int i = 1; i <= t; i++) p1 = p1*(1-s[i][0]); double p2 = 1; for(int i = 1; i <= t; i++) p2 = p2*(s[i][n-1]-s[i][0]); printf("%.3f\n",p1-p2); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。