【每日一题】比赛
比赛
https://ac.nowcoder.com/acm/problem/14734
题目
题目描述：你在打比赛，这场比赛总共有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嘞：
- 首先我们题目的重要信息有题目数和题目通过数量。那就决定了，dp[n][m]就是n个题过了m个题目的情况。
- 既然如此，我们下面最重要的就是把递推式求出来了。
- 那我们以第n个数是否答对为基准，将dp[n][m]的来源分成两部分：dp[n][m] = 第n个答对了 + 第n个答错了。
- 答对了会怎么样呢？说明第n这个位置占m中的一个位置：第n个答对了 = dp[n - 1][m - 1] 。
- 答错了会咋样嘞？说明第n个位置不被算在m中：第n个答错了 = dp[n - 1][m]。
- 那么递推式就出来了：dp[n][m] = dp[n - 1][m - 1] + dp[n - 1][m]。
- 这里要注意一点：m = 0的时候是没有前项的：dp[n][0] = dp[n - 1][0] * (1 - real[n])。
打代码：
- 先数组存下我们的所有数据。
- 然后遍历算出每一个数正确的概率。
- 然后就可以二进制枚举或者dp了。
- 看我代码趴~
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;
}
//动态规划
//函数区每日一题 文章被收录于专栏
憨憨的专栏
美团一面919人在聊