题目分析

题意解析

本题要求计算满足以下两个条件的概率： 1.所有团队至少解决一个问题。 2. 冠军团队至少解决 $N$ 个问题。

输入数据包括：

• $M$：问题总数（$0 < M \leq 30$）。
• $T$：团队总数（$1 < T \leq 1000$）。
• $N$：冠军团队至少需要解决的问题数量（$0 < N \leq M$）。
• $P_{ij}$：团队 $i$ 解决问题 $j$ 的概率（$0 \leq P_{ij} \leq 1$）。

解题思路

1.状态定义
定义 $dp[i][j][k]$ 为第 $i$ 个团队在前 $j$ 个问题中解决了 $k$ 个问题的概率。

2.状态转移方程
对于第 $i$ 个团队：

• 如果当前问题未被解决：
  $dp[i][j][k] = dp[i][j-1][k] \times (1 - P_{ij})$
• 如果当前问题被解决：
  $dp[i][j][k] = dp[i][j-1][k-1] \times P_{ij}$

3.预处理
计算每个团队在 $M$ 个问题中至少解决 $k$ 个问题的概率 $s[i][k]$，即：

4.最终概率计算

• 所有团队至少解决一个问题的概率：$$p_1 = \prod_{i=1}^{T} (s[i][M] - s[i][0])$$
• 所有团队最多解决 $N-1$ 个问题的概率：$$p_2 = \prod_{i=1}^{T} (s[i][N-1] - s[i][0])$$
• 目标概率：$$\text{Result} = p_1 - p_2$$

标程

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;

int M, T, N;   // M: 题数, T: 团队数, N: 冠军队至少做题数
double dp[1001][31][31];   // 状态方程: dp[i][j][k] 为第 i 队 PASS 前 j 题中的 k 题的概率
double p[1001][31];        // p[i][j] 为第 i 队通过第 j 题的概率
double s[1001][31];        // s[i][k] 为第 i 队在 M 题中至少 PASS k 题的概率

// 概率打表
void ProTable() {
    memset(dp, 0.0, sizeof(dp));
    memset(s, 0.0, sizeof(s));

    int i, j, k;
    for (i = 1; i <= T; i++) {  // 逐队枚举
        /* Initial */
        dp[i][0][0] = 1.0;

        for (j = 1; j <= M; j++)
            dp[i][j][0] = dp[i][j - 1][0] * (1 - p[i][j]);

        /* DP */
        for (j = 1; j <= M; j++)
            for (k = 1; k <= j; k++)
                dp[i][j][k] = dp[i][j - 1][k - 1] * p[i][j] + dp[i][j - 1][k] * (1 - p[i][j]);

        s[i][0] = dp[i][M][0];
        for (k = 1; k <= M; k++)
            s[i][k] = s[i][k - 1] + dp[i][M][k];
    }
    return;
}

int main() {
    while (cin >> M >> T >> N) {
        if (!M && !T && !N)
            break;

        /* Input */
        for (int i = 1; i <= T; i++)
            for (int j = 1; j <= M; j++)
                cin >> p[i][j];

        /* Compute the Probability */
        ProTable();

        double p1 = 1.0;
        for (int i = 1; i <= T; i++)
            p1 *= (s[i][M] - s[i][0]);  // 所有队至少做 1 题的概率

        double p2 = 1.0;
        for (int i = 1; i <= T; i++)
            p2 *= (s[i][N - 1] - s[i][0]);  // 所有队做的题数均在 1~N-1 之间的概率

        /* Output */
        cout << fixed << setprecision(3) << p1 - p2 << endl;
        // 每队至少解出一题 且 至少有一队(冠军队)能至少解出 N 道题的概率
    }
    return 0;
}