POJ 2151 Check the difficulty of problems

时间：2010-12-09 来源：ltang

首先计算所有队伍解决题目>=1的联合概率P0,计算所有队伍解决题目个数在[1,n-1]区间的联合概率Pn

dp求解每个队伍解题概率:dp[i][j]表示i题时解决j道题的概率,dp方程为

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

欢迎review

#include<iostream>
using namespace std;

int main()
{
    int i,j,M,T,N,p,q;
    double dp[31][31],ap[31],f0,fn,t;
    while(scanf("%d %d %d", &M, &T, &N)&&(M+T+N))
    {
        f0=1.0, fn=1.0;
        for(i=0;i<T;i++)
        {
            memset(dp,0,sizeof(dp));
            for(j=1;j<=M;j++)scanf("%lf", &ap[j]);
            dp[0][0]=1.0;
            for(p=1;p<=M;p++)
            {
                dp[p][0]=dp[p-1][0]*(1-ap[p]);
                for(q=1;(q<N)&&(q<=p);q++)
                    dp[p][q]=dp[p-1][q]*(1-ap[p])+dp[p-1][q-1]*ap[p];
            }
            f0*=(1-dp[M][0]);
            for(t=0,j=1;j<N;j++)t+=dp[M][j];
            fn*=t;
        }
        printf("%.3lf\n",f0-fn);
    }
    return 0;
}