首页 > 代码库 > poj 2151 Check the difficulty of problems （检查问题的难度）

poj 2151 Check the difficulty of problems （检查问题的难度）

2024-07-16 06:30:33   220人阅读

poj 2151 Check the difficulty of problems

http://poj.org/problem?id=2151

题意：此刻有tn道题目，有dn个队伍，知道每个队伍能答对每个题目的概率，问：冠军至少答对n（1<=n<=tn）道题目，其他队伍至少要答对一道题目的概率

dp+概率

方法：

f[i][j]第i队做对第j个题的概率

g[i][j][k]第i队前j个题做对k个题的概率

状态转移方程：g[i][j][k] = g[i][j-1][k-1]*f[i][j] + g[i][j-1][k]*(1-f[i][j])

 

 1 /* 2 Problem: 2151        User: bibier 3 Memory: 5120K        Time: 47MS 4 Language: G++        Result: Accepted 5 */ 6  7 #include <stdio.h> 8 #include <string.h> 9 #include <iostream>10 #include <algorithm>11 #include <cstdio>12 #include <cstring>13 #include <cmath>14 #include <stack>15 #include <queue>16 #include <vector>17 using namespace std;18 #define M 0x0f0f0f0f19 #define min(a,b) (a>b?b:a)20 #define max(a,b) (a>b?a:b)21 22 23 float f[1003][33];//f[i][j]第i队做对第j个题的概率24 float g[1003][33][33];//g[i][j][k]第i队前j个题做对k个题的概率25 26 //g[i][j][k] = g[i][j-1][k-1]*f[i][j] + g[i][j-1][k]*(1-f[i][j])27 int main()28 {29     int tn,dn,n;30     int i,j,k;31     while(scanf("%d %d %d",&tn,&dn,&n)!=EOF)32     {33         if(tn==0&&dn==0&&n==0)34             break;35         memset(g,0,sizeof(g));36         memset(f,0,sizeof(f));37 38         for(i=1; i<=dn; i++)39             for(j=1; j<=tn; j++)40                 scanf("%f",&f[i][j]);41 42         for(i=1; i<=dn; i++)43         {44             g[i][1][0]=1-f[i][1];45             g[i][1][1]=f[i][1];46         }47 48         for(i=1; i<=dn; i++)49             for(j=2; j<=tn; j++)50                 for(k=0; k<=j; k++)51                 {52                     if(k==j)53                         g[i][j][k] = g[i][j-1][k-1]*f[i][j];54                     else if(k==0)55                         g[i][j][k] = g[i][j-1][k]*(1-f[i][j]);56                     else57                         g[i][j][k] = g[i][j-1][k-1]*f[i][j] + g[i][j-1][k]*(1-f[i][j]);58                 }59         float all=1;60         for(i=1; i<=dn; i++) //每队至少做对一道题的最终概率61             all*=(1-g[i][tn][0]);62 63         float midall=1;64         for(i=1; i<=dn; i++)65         {66             float everyd=0;67             for(j=1; j<n; j++)68             {69                 everyd+=g[i][tn][j];70             }71             midall*=everyd;72         }73         all-=midall;74         printf("%.3f\n",all);75     }76     return 0;77 }
View Code

 


联系
我们