首页 > 代码库 > poj2151（Check the difficulty of problems）

poj2151（Check the difficulty of problems）

2024-07-13 18:36:31   221人阅读

题目地址：Check the difficulty of problems

 

题目大意：

    在编程比赛中有M个题，T支队伍。要求冠军团队至少做出N道题。

    求每对至少做出一道题的同时冠军队至少做出N道题的概率。

 

解题思路：

    概率+DP。首先做的是将题目求的概率转化成：每队均至少做一题的概率P1 减去 每队做题数均在1到N-1之间的概率P2 。


然后求出p1和p2.下面是转到一份网上详解。

 

 

代码：

     

 1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector>10 #include <queue>11 #include <stack>12 #include <cmath>13 #include <list>14 #include <map>15 #include <set>16 using namespace std;17 /***************************************/18 #define ll long long19 #define int64 __int6420 /***************************************/21 const int INF = 0x7f7f7f7f;22 const double eps = 1e-8;23 const double PIE=acos(-1.0);24 const int dx[]= {0,-1,0,1};25 const int dy[]= {1,0,-1,0};26 const int fx[]= {-1,-1,-1,0,0,1,1,1};27 const int fy[]= {-1,0,1,-1,1,-1,0,1};28 /***************************************/29 void openfile()30 {31     freopen("data.in","rb",stdin);32     freopen("data.out","wb",stdout);33 }34 /**********************华丽丽的分割线,以上为模板部分*****************/35 double p[1001][35],dp[1001][35][35],s[1001][35];36 int main()37 {38     int m,t,n;39     while(scanf("%d%d%d",&m,&t,&n)&&(m+t+n))40     {41         memset(p,0,sizeof(p));42         memset(dp,0,sizeof(dp));43         memset(s,0,sizeof(s));44         int i,j,k;45         double ce=1.0,sum=0;46         for(i=1;i<=t;i++)47             for(j=1;j<=m;j++)48                 scanf("%lf",&p[i][j]);49         for(i=1;i<=t;i++)50         {51             dp[i][0][0]=1.0;52             for(j=1;j<=m;j++)53             {54                 dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);55             }56             for(j=1;j<=m;j++)57             {58                 for(k=1;k<=j;k++)59                 {60                     dp[i][j][k]=dp[i][j-1][k]*(1-p[i][j])+dp[i][j-1][k-1]*p[i][j];61                 }62             }63             s[i][0]=dp[i][m][0];64             for(j=1;j<=m;j++)65             {66                 s[i][j]=s[i][j-1]+dp[i][m][j];67             }68         }69         double p1=1.0,p2=1.0;70         for(i=1;i<=t;i++)71             p1*=(s[i][m]-s[i][0]);72         for(i=1;i<=t;i++)73             p2*=(s[i][n-1]-s[i][0]);74         printf("%.3lf\n",p1-p2);75     }76     return 0;77 }
View Code


联系
我们