Educational DP Contest : I – Coins 题解

主要思路

概率 DP,显然地。

我们怎么来统计呢?在存下概率之后,我们枚举轮数并且枚举硬币向上的情况,之后转移即可,代码里一目了然。

代码

// I.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3030;
int n;
double prob[MAX_N], dp[MAX_N][MAX_N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &prob[i]);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i; j++)
        {
            int x = j, y = i - j;
            if (x)
                dp[x][y] += dp[x - 1][y] * prob[i];
            if (y)
                dp[x][y] += dp[x][y - 1] * (1 - prob[i]);
        }
    double ans = 0;
    for (int i = 0; n - i > i; i++)
        ans += dp[n - i][i];
    printf("%.10lf", ans);
    return 0;
}

概率 & 数学期望

目录

  • 概述
  • 概率
    • 概率相关的概念
    • 概率的意义
    • 同时发生的概率
    • 概率的公理 & 命题
    • 条件概率
      • 概念
      • 全概率公式
      • 贝叶斯公式
      • 例题
    • 随机变量
    • 概率在 OI 中的应用
  • 数学期望
    • 数学期望的概念
    • 数学期望的线性性 & 递推
    • 数学期望在 OI 中的应用

继续阅读概率 & 数学期望