poj 2151Check the difficulty of problems<概率DP>

链接：http://poj.org/problem?id=2151

题意：一场比赛有 T 支队伍，共 M 道题， 给出每支队伍能解出各题的概率~

　　  求 ：冠军至少做出 N 题且每队至少做出一题的概率~

思路：设dp[i][j][k] 为 第 i 队 在前 j 题共解出 k 题的概率~

　　　那么 dp[i][j][k]=dp[i][j-1][k-1]*p[i][j-1] + dp[i][j-1][k]*(1-p[i][j-1]) ~

　　   s[i][0] 为 第 i 队至多解出N-1题的概率，s[i][1] 为第 i 队至少解出一题的概率~

　　　那么就可以解出来了~

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int M, T, N;
double dp[1005][35][35], s[1005][2], p[1005][35];
int main( )
{
    while(scanf("%d%d%d", &M, &T, &N)!= EOF, M+N+T){
        for( int i=0; i<T; ++ i ){
            for( int j=0; j<M; ++ j ){
                scanf("%lf", &p[i][j]);
            }
        }
        memset(dp, 0, sizeof dp);
        memset(s, 0, sizeof s);
        double p1=1,p2=1;
        for( int i=0; i<T; ++ i ){
            dp[i][0][0]=1;
            for( int j=1; j<=M; ++ j ){
                for( int k=0; k<=j; ++ k ){
                    dp[i][j][k]=dp[i][j-1][k-1]*p[i][j-1]+dp[i][j-1][k]*(1-p[i][j-1]);
                    if(j==M && k>0){
                        s[i][1]+=dp[i][j][k];

                        if(k<N){
                            s[i][0]+=dp[i][j][k];
                        }
                    }
                }
            }

            p1*=s[i][1];
            p2*=s[i][0];
        }
        printf("%.3f
", p1-p2);
    }
    return 0;
}