Link

传送门

Problem

Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms:
1. All of the teams solve at least one problem.
2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.

Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.

Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?

Mean

一次编程比赛有M道题,T支队伍参加。已知每支队伍能做出每道题的概率,求所有队伍都能做出至少一道题&&题数最多的队伍做出大于等于N道题的概率。

Analysis

概率DP.

can[i][j]表示第i支队伍做出第j道题的概率,dp[i][j][k]表示第i支队伍的前j道题共做出k个的概率。那么有状态转移方程:dp[i][j][k] = dp[i][j-1][k] * (1 – can[i][j]) + dp[i][j-1][k-1] * can[i][j];

最终答案是:所有队伍做出一道题以上的概率 减去 所有队伍做出[1, N)道题的概率。

Code

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 35, maxt = 1024;
int M, T, N;
double can[maxt][maxn];
double dp[maxt][maxn][maxn];

int main() {
    while(~scanf("%d%d%d", &M, &T, &N), M||T||N) {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= T; ++i)
            for(int j = 1; j <= M; ++j)
                scanf("%lf", &can[i][j]);
        for(int i = 1; i <= T; ++i) {
            dp[i][0][0] = 1;
            for(int j = 1; j <= M; ++j) {
                dp[i][j][0] = dp[i][j-1][0] * (1 - can[i][j]);
                for(int k = 1; k <= j; ++k) {
                    dp[i][j][k] = dp[i][j-1][k] * (1 - can[i][j]) + dp[i][j-1][k-1] * can[i][j];
                }
            }
        }
        double ans1 = 1;
        for(int i = 1; i <= T; ++i)
            ans1 *= 1.0 - dp[i][M][0];
        double ans2 = 1;
        for(int i = 1; i <= T; ++i) {
            double sum = 0;
            for(int j = 1; j < N; ++j)
                sum += dp[i][M][j];
            ans2 *= sum;
        }
        printf("%.3f\n", ans1 - ans2);
    }
    return 0;
}

欢迎留言