poj 2151 Check the difficulty of problems (概率dp)

poj 2151 Check the difficulty of problems (概率dp)

/*
一次比賽中，共M道題，T個隊，p[i][j]表示隊i解出題j的概率；問每隊至少解出一題且冠軍隊至少解出N道題的概率。
dp[i][j][k]表示第i支隊伍在前j道題中解出k道的概率


問題的解可以轉化為：每隊均至少做一題的概率（用P1表示）減去每隊做題數均在1到N-1
之間的概率（用P2表示）。
*/
# include 
# include 
# include 
# include 
using namespace std;
double dp[1010][35][35];
double p[1010][35];
int main()
{
    int i,j,k,n,t,m;
    while(~scanf("%d%d%d",&m,&t,&n),m+t+n)
    {
        for(i=1; i<=t; i++)
        {
            for(j=1; j<=m; j++)
                scanf("%lf",&p[i][j]);
        }
        memset(dp,0,sizeof(dp));
        for(i=1; i<=t; i++)
        {
            dp[i][0][0]=1;
            for(j=1; j<=m; j++)
            {
                dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);
                for(k=1; k<=m; k++)
                {
                    dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]);
                }
            }
        }
        double p1=1,p2=1;
        for(i=1;i<=t;i++)///每隊至少做一題的概率
            p1*=1-dp[i][m][0];
        double sum=0;
        for(i=1;i<=t;i++)///每隊做題數均在1到N-1之間的概率
        {
            sum=0;
            for(j=1;j<=n-1;j++)///單獨一支隊伍,同支隊伍是用+
               sum+=dp[i][m][j];
            p2*=sum;
        }
        printf("%.3lf\n",p1-p2);
    }
    return 0;
}