【每日一题】【5月19日】比赛

题意：

比赛中有 $12$ 道题。对于第 $i$ 道题，你有 $a_i$ 的概率自己解出来，有 $b_i$ 的概率从左边队伍听到题解，有 $c_i$ 的概率从右边的队伍听到题解。
问解出 $0 - 12$ 道题的概率各是多少？

解法：

枚举
对于第 $i$ 道题，最终能解出来的概率为 $1 - (1 - a_i)(1 - b_i)(1 - c_i)$ 。
然后二进制枚举每道题是/否解出来，计算对应情况的概率，加到对应题数
复杂度为 $O(2^{12} \times 12)$

$dp[i][j]$ 表示前 $i$ 个问题，解出 $j$ 个的概率。

初始化 $dp[0][0] = 1$

转移方程为：

$dp[i][0] = dp[i - 1][0] \times (1 - p[i])$
$dp[i][j] = dp[i - 1][j] \times (1 - p[i]) + dp[i - 1][j - 1] \times p[i]$

Code：

枚举

#include <bits/stdc++.h>
using namespace std;
double a[12], b[12], c[12], p[12], ans[13];
int main() {
    for(int i = 0; i < 12; i++) cin >> a[i];
    for(int i = 0; i < 12; i++) cin >> b[i];
    for(int i = 0; i < 12; i++) cin >> c[i];
    for(int i = 0; i < 12; i++) p[i] = 1 - (1 - a[i]) * (1 - b[i]) * (1 - c[i]);
    for(int i = 0; i < 1 << 12; i++) {
        double tmp = 1.0;
        int k = 0;
        for(int j = 0; j < 12; j++) {
            if(i >> j & 1) k++, tmp *= p[j];
            else tmp *= 1 - p[j];
        }
        ans[k] += tmp;
    }
    cout << fixed << setprecision(6);
    for(int i = 0; i <= 12; i++) cout << ans[i] << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
double a[13], b[13], c[13], p[13], dp[13][13];
int main() {
    for(int i = 1; i <= 12; i++) cin >> a[i];
    for(int i = 1; i <= 12; i++) cin >> b[i];
    for(int i = 1; i <= 12; i++) cin >> c[i];
    for(int i = 1; i <= 12; i++) p[i] = 1 - (1 - a[i]) * (1 - b[i]) * (1 - c[i]);
    dp[0][0] = 1;
    for(int i = 1; i <= 12; i++) {
        dp[i][0] = dp[i - 1][0] * (1 - p[i]);
        for(int j = 1; j <= 12; j++) dp[i][j] = dp[i - 1][j] * (1 - p[i]) + dp[i - 1][j - 1] * p[i];
    }
    cout << fixed << setprecision(6);
    for(int i = 0; i <= 12; i++) cout << dp[12][i] << endl;
    return 0;
}