题目

题目描述：
你在打比赛，这场比赛总共有12个题
对于第i个题，你的队伍有a[i]的几率解决她，如果解决不了她呢？
由于所有人讨论的都很大声
所以你有b[i]的概率从左边那个队那里听会这个题的做法
有c[i]的概率从右边那个队那里听会这个题的做法
请问最终你们队伍解出0-12题的概率分别是多少

输入描述：
第一行12个数表示a[1] -> a[12]
第二行12个数表示b[1] -> b[12]
第三行12个数表示c[1] -> c[12]

输出描述：
输出13行，第i行表示解出i-1题的概率
保留6位小数

解析

首先我们仔仔细细看看题！我一开始还在质疑只有12个题，为啥会出13个答案，为啥还有第零题。。。
最后一句的意思是：你解出一共n道题的概率是多少，不是每道题的概率（每道题的概率也太简单了。

这道题可以用二进制枚举直接判断将每道题目正误的两种情况。然后把所有情况相加，212的计算量不大，所以可行。

概率计算：
高中数学我就不多说了吧，就是总概率 - 我既没写出来 * 也没偷听到左边的 * 也没偷听到右边的：real[i] = 1 - (1 - a[i]) * (1 - b[i]) * (1 - c[i])。

但是我们这道题二进制枚举的话时间复杂度是O(2n)，所以我们这里还是用dp来写，时间复杂度为O(n2)。
  • 动态规划最重要的就是递推和dp数组的含义。

dp嘞：
  1. 首先我们题目的重要信息有题目数和题目通过数量。那就决定了，dp[n][m]就是n个题过了m个题目的情况。
  2. 既然如此，我们下面最重要的就是把递推式求出来了。
  3. 那我们以第n个数是否答对为基准，将dp[n][m]的来源分成两部分：dp[n][m] = 第n个答对了 + 第n个答错了。
  4. 答对了会怎么样呢？说明第n这个位置占m中的一个位置：第n个答对了 = dp[n - 1][m - 1] 。
  5. 答错了会咋样嘞？说明第n个位置不被算在m中：第n个答错了 = dp[n - 1][m]。
  6. 那么递推式就出来了：dp[n][m] = dp[n - 1][m - 1]  + dp[n - 1][m]。
  7. 这里要注意一点：m = 0的时候是没有前项的：dp[n][0] = dp[n - 1][0] * (1 - real[n])。

打代码：
  1. 先数组存下我们的所有数据。
  2. 然后遍历算出每一个数正确的概率。
  3. 然后就可以二进制枚举或者dp了。
  4. 看我代码趴~

AC代码 

#include <iostream> 
using namespace std; 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
//代码预处理区 
const int MAX = 13; 
double a[MAX], b[MAX], c[MAX], real[MAX]; 
double dp[MAX][MAX], ans[MAX]; 
//全局变量区 
/* int main() { 
    for (int i = 1; i <= 12; i++) scanf("%lf", &a[i]); 
    for (int i = 1; i <= 12; i++) scanf("%lf", &b[i]); 
    for (int i = 1; i <= 12; i++) scanf("%lf", &c[i]); 
    for (int i = 1; i <= 12; i++) real[i] = 1 - (1 - a[i]) * (1 - b[i]) * (1 - c[i]); 
    for (int i = 0; i < (1 << 12); i++) { 
        int cnt = 0; 
        double mul = 1; 
        for (int j = 0; j < 12; j++) 
            if ((1 << j) & i) { 
                cnt++; 
                mul *= real[j + 1]; 
            } 
            else mul *= 1 - real[j + 1]; 
        ans[cnt] += mul; 
    } 
    for (int i = 0; i <= 12; i++) printf("%.6f\n", ans[i]); 
    return 0; 
} */ 
//二进制枚举
int main() { 
    for (int i = 1; i <= 12; i++) scanf("%lf", &a[i]); 
    for (int i = 1; i <= 12; i++) scanf("%lf", &b[i]); 
    for (int i = 1; i <= 12; i++) scanf("%lf", &c[i]); 
    for (int i = 1; i <= 12; i++) real[i] = 1 - (1 - a[i]) * (1 - b[i]) * (1 - c[i]); 
    dp[0][0] = 1; 
    for (int i = 1; i <= 12; i++) 
        for (int j = 0; j <= i; j++) 
            if (!j) dp[i][j] = dp[i - 1][j] * (1 - real[i]); 
            else dp[i][j] = dp[i - 1][j] * (1 - real[i]) + dp[i - 1][j - 1] * real[i]; 
    for (int i = 0; i <= 12; i++) 
        printf("%.6f\n", dp[12][i]); 
    return 0; 
} 
//动态规划
//函数区