poj 2151 Check the difficulty of problems（概率dp）

时间：2024-01-20 14:19:15

poj double 就得交c++，我交G++错了一次

题目：http://poj.org/problem?id=2151

题意：ACM比赛中，共M道题，T个队，pij表示第i队解出第j题的概率

问 每队至少解出一题且冠军队至少解出N道题的概率。

每队均至少做一题的概率P1 减去 每队做题数均在1到N-1之间的概率P2

设dp[i][j][k]表示第i个队在前j道题中解出k道的概率

则：

dp[i][j][k]=dp[i][j-1][k-1]*p[j][k]+dp[i][j-1][k]*(1-p[j][k]);

先初始化算出dp[i][0][0]和dp[i][j][0];

设s[i][k]表示第i队做出的题小于等于k的概率

则s[i][k]=dp[i][M][0]+dp[i][M][1]+``````+dp[i][M][k];

则每个队至少做出一道题概率为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]);

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<stack>

 #include<queue>

 #include<iomanip>

 #include<cmath>

 #include<map>

 #include<vector>

 #include<algorithm>

 using namespace std;

 double dp[][][],s[][],p[][];

 int main()

 {

     int m,n,t,i,j,k;

     double p1,p2;

     while(cin>>m>>t>>n)

     {

         if(m==&&n==&&t==)

         break;

         for(i=; i<=t; i++)

         for(j=; j<=m; j++)

         cin>>p[i][j];

         for(i=; i<=t; i++)

         {

             dp[i][][]=;

             for(j=; j<=m; j++)

             dp[i][j][]=dp[i][j-][]*(-p[i][j]);

             for(j=; j<=m; j++)

             for(k=; k<=j; k++)

             dp[i][j][k]=dp[i][j-][k-]*p[i][j]+dp[i][j-][k]*(-p[i][j]);

             s[i][]=dp[i][m][];

             for(k=; k<=m; k++)

             s[i][k]=s[i][k-]+dp[i][m][k];

         }

         p1=; p2=;

         for(i=; i<=t; i++)

         {

             p1*=(-s[i][]);

             p2*=(s[i][n-]-s[i][]);

         }

         printf("%.3lf\n",p1-p2);

     }

     return ;

 }

相关文章