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

时间：2022-08-09 19:10:53

题意：给出m、t、n，接着给出t行m列，表示第i个队伍解决第j题的概率。
现在让你求：每个队伍都至少解出1题，且解出题目最多的队伍至少要解出n道题的概率是多少？

思路：求补集。
即所有队伍都解出题目的概率，减去所有队伍解出的题数在1~n-1之间的概率

这里关键是如何求出某个队伍解出的题数在1~n-1之间的概率，采用dp的方法：

用p(i,j)表示前i道题能解出j道的概率，有
p(i,j)=p(i-1,j)*(1-p(i))+p(i-1,j-1)*p(i)
p(i)表示解出第i题的概率。

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

using namespace std;

const int maxT=+;

const int maxm=;

int m,t,n;

double prob[maxm]; //存储队伍解决第i道题的概率

double p[maxm][maxm]; //p[i][j]表示某队伍前i道题解决了j道题的概率

double pb[maxT]; //pb[i]存储第i个队伍解出的题数在1~n-1之间的概率

double ret; //所有队伍都解出题的概率

int main() {

    while(scanf("%d%d%d",&m,&t,&n)!=EOF) {

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

            break;

        ret=;

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

            p[][]=;

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

                scanf("%lf",&prob[j]);

                p[j][]=p[j-][]*(-prob[j]);

                p[j][j]=p[j-][j-]*prob[j];

            }

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

                for(int r=; r<k; r++) {

                    p[k][r]=p[k-][r-]*(prob[k])+p[k-][r]*(-prob[k]);

                }

            }

            pb[i]=;

            for(int j=; j<=n-; j++) {

                pb[i]+=p[m][j];

            }

            ret*=(-p[m][]);

        }

        double sum=; //求所有队伍解出的题数在1~n-1之间的概率

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

            sum*=pb[i];

        }

        double ans=ret-sum;

        printf("%.3lf\n",ans);

    }

    return ;

}

相关文章