poj2151Check the difficulty of problems

xiaoxiao2021-02-28  83

Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms: 1. All of the teams solve at least one problem. 2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.

Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.

Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?




这道题就是个数学题啊 参考了这位大牛的代码: http://blog.csdn.net/i_want_to_be_a_god/article/details/25926243

#include<iostream> using namespace std; #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<stdlib.h> #include<vector> #include<queue> #include<deque> #include<map> #include<set> #include<time.h> #define pi(x,y) printf("%d%c",(x),(y)); #define pin(x) printf("%d\n",(x)); #define si(x) scanf("%d",&(x)) #define sii(x,y) scanf("%d%d",&(x),&(y)) #define s3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define rep(x,y,z) for(int (x)=(y);(x)<(z);++(x)) #define dep(x,y,z) for(int (x)=(y)-1;(x)>=(z);--(x)) #define read int TcaseN;scanf("%d",&TcaseN);for(int Tcase=1;Tcase<=TcaseN;++Tcase) #define cls(x,y) memset((x),(y),sizeof((x))); #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define max3(value_a,value_b,value_c) max(max(value_a,value_b),value_c) #define min3(value_a,value_b,value_c) min(min(value_a,value_b),value_c) #define GT(x) (x)=clock(); #define fin(x) freopen(x,"r",stdin); #define fout(x) freopen(x,"w",stdout); ///In This You Can Define Long Integer Type #define LONGTYPE long long typedef LONGTYPE LL; typedef unsigned LONGTYPE ULL; const int maxint=((~((unsigned)(0)))>>1); const LL maxll=((~((unsigned LONGTYPE)(0)))>>1); const int inf=0x3f3f3f3f; const double PI=acos(-1.0); const int N=1005; const int M=35; double p[N][M],dp[M][M]; int m,t,n; int main() { #ifdef tangge clock_t tSTART,tEND,t3; GT(tSTART); #endif // tangge /*Input:*/ while(scanf("%d%d%d",&m,&t,&n),m+t+n){ for(int i=1;i<=t;++i){ for(int j=1;j<=m;++j){ scanf("%lf",&p[i][j]); } } double all=1;//ÿ¸ö¶ÓÖÁÉÙ×ö³öÒ»ÌâµÄ¸ÅÂÊ double tmp2=1; memset(dp,0,sizeof(dp)); dp[0][0]=1.00; for(int i=1;i<=t;++i){ double tmp=1.00;//µÚi¶ÓÒ»ÌⶼûÓÐ×ö³öÀ´µÄ¸ÅÂÊ for(int j=1;j<=m;++j){ tmp*=(1-p[i][j]); for(int k=0;k<=j;++k){ dp[j][k]=((k>0)?(dp[j-1][k-1]*p[i][j]):0)+dp[j-1][k]*(1-p[i][j]); } } double tmp1=0.00;//µÚi¶Ó×ö³ö1 ~ n-1ÌâµÄ¸ÅÂÊ for(int k=1;k<n;++k){ tmp1+=dp[m][k]; } tmp2*=tmp1; all*=(1-tmp); } printf("%.3f\n",all-tmp2); } #ifdef tangge GT(tEND); printf("%.8lf\n",(tEND-tSTART)/1000.0); #endif // tangge return 0; }
转载请注明原文地址: https://www.6miu.com/read-76590.html

最新回复(0)