Educational DP Contest : J – Sushi 题解

主要思路

啊呀,我太菜了。

因为每盘的寿司数量最多为3,所以我们可以三个参数分别代表寿司数量为\(i\)的盘数。然后我们可以得出这样的方程:

\[ tot = A + B + C, dp(A,B,C) = \frac{n}{tot} + \frac{A}{tot}*dp(A-1,B,C) + \frac{B}{tot}*dp(A+1,B-1,C) + \frac{C}{tot}*dp(A,B+1,C-1) \]

因为没有固定的顺序进行 DP,所以我们进行记忆化搜索即可。

代码

// J.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 330;
int n, ai[MAX_N], sushi[4];
double dp[MAX_N][MAX_N][MAX_N];
double dfs(int a, int b, int c)
{
    if (a == 0 && b == 0 && c == 0)
        return 0;
    if (dp[a][b][c] >= 0)
        return dp[a][b][c];
    double d = a + b + c, ans = n / d;
    if (a)
        ans += dfs(a - 1, b, c) * a / d;
    if (b)
        ans += dfs(a + 1, b - 1, c) * b / d;
    if (c)
        ans += dfs(a, b + 1, c - 1) * c / d;
    return dp[a][b][c] = ans;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), sushi[ai[i]]++;
    printf("%.10lf", dfs(sushi[1], sushi[2], sushi[3]));
    return 0;
}

概率 & 数学期望

目录

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

继续阅读概率 & 数学期望

数学期望和其线性性质

背景

自从NOIp 2018初赛第一次知道有数学期望这个东西起,我就一直很难理解。我一直没有去仔细的了解数学期望,而今天打了一场比赛,被逼着去了解了,现在我来写点东西记录一下这个概念。

概念介绍

\(数学期望\)是一个跟概率相关的概念。他的定义是:

数学期望是一个有限的事件的结果乘上一个事件的概率。

我们可以通过举例子来解释这个概念。比如取一个随机数(1-10之间),那么取到5的数学期望就是\(\frac {1} {2}\)。一般,我们用\(\mathbb{E}\)来表示这个值。

性质介绍

在本篇文章中,我只介绍一个性质。未来如果我学到了一些关于数学期望的新东西,那么我会把这些内容写在这篇文章里的。

数学期望在OI中比较重要的性质就是其线性性。简单来讲,如果有两个事件的数学期望为\(\mathbb{E}(a)\)和\(\mathbb{E}(b)\),那么这两个事件叠加起来就是\(\mathbb{E}(a) + \mathbb{E}(b) = \mathbb{E}(a+b)\)。这个性质在OI中比较重要,一些题目会利用这个性质让解题者使用递推的方式解出答案。接下来我们看一道题目:

例题

链接:T2062:随机数生成器

这道题目是我在华南师范大学附属中学举办的比赛中遇到的题目。虽然我这一题并没有AC,但是不妨碍我们来解释数学期望的一些性质和递推得解的方法。

我们来思考这样一个方程,设置\(\mathbb{E}(i)\)为输入为\(i\)的数学期望,那么,根据数学期望的线性性质,我们可以很容易推出以下方程:\[\mathbb{E}(i) =\frac {\mathbb{E}(1) + 1}{i} + \frac {\mathbb{E}(2) + 1}{i} + \frac {\mathbb{E}(3) + 1}{i} + \frac {\mathbb{E}(4) + 1}{i} + \dots + \frac {\mathbb{E}(i) + 1}{i}\]

而在本题中,可知\(\mathbb{E}(1) = 0\)。那么我们来变换一下式子,变成:\[\mathbb{E}(i) = \frac {\mathbb{E}(1) + \mathbb{E}(2) + \dots + \mathbb{E}(i – 1) + i}{n – 1}\]这样我们就可以递推出式子。

数学期望是OI中常见的概念,掌握它很有帮助。建议读者可以自己去阅读相关的资料,我在这里便不再描述。