POJ 2151 Check the difficulty of problems

题意：一场ACM比赛有T支队伍参加，一共有m道题，给出每个队伍解出每一道题的可能性。求每只队伍至少解决一道题，且至少有一支队伍解决的问题数大于等于n的概率。(0 < M <= 30，1 < T <= 1000，0 < N <= M)

解法：概率DP。设d[i][j][k]表示第i支队伍，前j道题，解出k道的概率。则d[i][j][k] = d[i][j-1][k-1] * p[i][j] + d[i][j-1][k] * p[i][j]。

　　　然后ans1 = ∏(1 - d[i][m][0])(0 <= i <= T)，ans2 = ∏(d[i][m][1] + d[i][m][2] + ... + d[i][m][n-1])(0 <= i <= T)，所求为ans1 - ans2。

tag：概率DP

/*
 * Author:  Plumrain
 * Created Time:  2013-11-14 23:07
 * File Name: DP-POJ-2151.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define CLR(x) memset(x, 0, sizeof(x))

double p[1005][100], d[1005][40][40];

int main()
{
    int m, t, n;
    while (scanf ("%d%d%d", &m, &t, &n) != EOF && m){
        for (int i = 0; i < t; ++ i)
            for (int j = 1; j <= m; ++ j)
                scanf ("%lf", &p[i][j]);

        CLR (d);
        for (int i = 0; i < t; ++ i){
            d[i][0][0] = 1;
            for (int j = 1; j <= m; ++ j)
                for (int k = 0; k <= m; ++ k){
                    d[i][j][k] = d[i][j-1][k] * (1 - p[i][j]);
                    if (!k) continue;
                    d[i][j][k] += d[i][j-1][k-1] * p[i][j];
                }
        }

        double ans = 1.0;
        for (int i = 0; i < t; ++ i)
            ans *= (1 - d[i][m][0]);
        double tmp = 1.0;
        for (int i = 0; i < t; ++ i){
            double sum = 0.0;
            for (int j = 1; j < n; ++ j)
                sum += d[i][m][j];
            tmp *= sum;
        }
        ans -= tmp;
        printf ("%.3f
", ans);
    }
    return 0;
}