首页 > 代码库 > POJ 2151 Check the difficulty of problems （概率dp）

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

2024-07-03 23:31:07   221人阅读

题意：给出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=1000+5;
const int maxm=35;
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==0 && t==0 && n==0)
            break;
        ret=1;
        for(int i=0; i<t; i++) {
            p[0][0]=1;
            for(int j=1; j<=m; j++) {
                scanf("%lf",&prob[j]);
                p[j][0]=p[j-1][0]*(1-prob[j]);
                p[j][j]=p[j-1][j-1]*prob[j];
            }
            for(int k=1; k<=m; k++) {
                for(int r=1; r<k; r++) {
                    p[k][r]=p[k-1][r-1]*(prob[k])+p[k-1][r]*(1-prob[k]);
                }
            }
            pb[i]=0;
            for(int j=1; j<=n-1; j++) {
                pb[i]+=p[m][j];
            }
            ret*=(1-p[m][0]);
        }
        double sum=1; //求所有队伍解出的题数在1~n-1之间的概率
        for(int i=0; i<t; i++) {
            sum*=pb[i];
        }
        double ans=ret-sum;
        printf("%.3lf\n",ans);

    }
    return 0;
}
View Code

 


联系
我们