期望dp

题目

题意

有$n$个盘子分别为$1, 2, …, n$，每个盘子里初始装了$a_i(1 \leq a_i \leq 3)$块蛋糕，每次按照下面的方法吃蛋糕，直到蛋糕吃完

每次等概率的从$n$个盘子中挑选一个，假设选择了第$i$个盘子，如果该盘子中有蛋糕，那么就吃掉一个；如果没有，那就什么也不做

求出吃掉所有蛋糕的期望次数

数据范围

$1 \leq n \leq 300$

$1 \leq a_i \leq 3$

题解

思路

只有$4$种盘子，盘子里有$1, 2, 3$块蛋糕的盘子和空盘子，由于一共只有$n$个盘子，所以我们知道其中$3$种盘子的数量，就可以推出另一种盘子的数量

又盘子数最多为$300$，那我们以每种盘子的数量为状态来设计$dp$方程

设$dp[a][b][c]$为有$1$块蛋糕的盘子数量为$a$，有$2$块蛋糕的盘子数量为$b$，有三块蛋糕的盘子数量为$c$，从当前状态出发要把蛋糕全吃完的期望次数

既然我们的实际结束状态为$dp[0][0][0]$，我们应该在$dp$中把它设为初始状态(因为它不会转移到自己，肯定是0)

那我们的转移应该是

$\begin{align} dp[a][b][c] & = (dp[a - 1][b][c] + 1) \times \frac{a}{n} \\ & + (dp[a + 1][b - 1][c] + 1) \times \frac{b}{n} \\ & + (dp[a][b + 1][c - 1] + 1) \times \frac{c}{n} \\ & + (dp[a][b][c] + 1) \times \frac{n - a - b - c}{n} \\ \end{align}$

然后我们就发现这个东西是不可以直接枚举的，不管你正序还是倒序枚举，都会出现后效性，因为$a$同时依赖于$a - 1, a + 1$， $b$同理，那我们改写一下这个式子

$\begin{align} (dp[a + 1][b - 1][c] + 1) \times \frac{b}{n} & = (dp[a - 1][b][c] + 1) \times \frac{a}{n} \\ & + (dp[a][b + 1][c - 1] + 1) \times \frac{c}{n} \\ & + (dp[a][b][c] + 1) \times \frac{n - a - b - c}{n} \\ & - dp[a][b][c] \end{align}$

根据和式的交换律，我们用$a - 1$替换$a$， $b + 1$替换$b$， 注意，这样还原之后默认$a$大于等于$1$

$\begin{align} dp[a][b][c] \times \frac{b + 1}{n} & = (dp[a - 2][b + 1][c] + 1) \times \frac{a - 1}{n} \\ & + (dp[a - 1][b + 2][c] + 1) \times \frac{c}{n} \\ & + (dp[a - 1][b + 1][c] + 1) \times \frac{n - (a - 1) - (b + 1) - c}{n} \\ & - dp[a - 1][b + 1][c] \\ \end{align}$

由于我们默认$a$大于等于1，所以我们需要额外处理$a = 0$的情况，然后你就会发现还是有后效性

虽然学长说有些$dp$就是有后效性，这个时候可以列方程用高斯消元解决，但是我不会啊

优化

既然这样设计$dp$存在后效性，那我们就改一下$dp$方程的含义，注意到我们每次有效操作，一定会有一种盘子数量减少$1$，相邻种类的盘子数量增加$1$，也就是说他们的数量和是不变的

那我们设计新状态$dp[a][b][c$]表示有$3$块蛋糕的盘子数量为$c$，有$2$块和$3$块的盘子的数量和为$b$，有$1, 2, 3$块盘子的数量和为$a$到$dp[0][0][0$]的期望次数

那么转移方程为

$\begin{align} dp[a][b][c] & = (dp[a - 1][b][c] + 1) \times \frac{a - b}{n} \\ & + (dp[a][b - 1][c] + 1) \times \frac{b - c}{n} \\ & + (dp[a][b][c - 1] + 1) \times \frac{c}{n} \\ & + (dp[a][b][c] + 1) \times \frac{n - a}{n} \\ \end{align}$

$a$从$1$到$n$枚举， $b, c$都是$0$到$n$，过程中保证不越界并且$c \leq b \leq a$

代码

#include <iostream>
#include <cstdio>
#include <cstring>

int n;
int p[4];
long double f[302][302][302];

long double F(int i, int j, int k)
{
    if(i < 0 || j < 0 || k < 0) return 0;

    return f[i][j][k] + 1.0;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int tmp;
        scanf("%d", &tmp);

        p[tmp] ++;
    }

    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= i; j ++)
            for(int k = 0; k <= j; k ++)
            {
                long double tmp1 = F(i - 1, j, k) * (1.0 * i - j) / n;
                long double tmp2 = F(i, j - 1, k) * (1.0 * j - k) / n;
                long double tmp3 = F(i, j, k - 1) * 1.0 * k / n;
                long double tmp4 = 1.0 - 1.0 * i / n;
                long double tmp5 = 1.0 * n / i;

                f[i][j][k] = (tmp1 + tmp2 + tmp3 + tmp4) * tmp5;
            }

    double ans = f[n][p[2] + p[3]][p[3]];

    printf("%.12lf\n", ans);

    return 0;
}

浅谈期望$dp$

详解本题

状态设计

以本题为例，我们最终的目标是把所有的蛋糕都吃掉，也就是说让所有的盘子都变成空盘子，我们的实际操作中，初始状态是$f[n][p[2] + p[3]][p[3]]$，目标状态是$f[0][0][0]$，那么我们的$dp$状态应该表示什么呢，应该有两种表示方法

$f[i][j][k]$表示从$f[n][p[2] + p[3]][p[3]]$到$f[i][j][k]$所期望的步数
$f[i][j][k]$表示$f[i][j][k]$到$f[0][0][0]$的期望步数

第一种设法

这样的话我们$dp$的初始状态为$f[n][p[2] + p[3]][p[3]]$，然后往别的状态转移，直到$f[0][0][0]$

但是这样会出现问题，那就是$f[n][p[2] + p[3]][p[3]]$并不为$0$，因为它虽然是初始状态，但是它可以转移到自己，那它的期望就肯定不是$0$，不好算

而且$f[0][0][0]$是转移不到自己的，还得特判

第二种设法

这种设法，我们$dp$的初始状态为$f[0][0][0]$，然后往别的状态转移，直到$f[n][p[2] + p[3]][p[3]]$

这种设法的话$f[0][0][0] = 0$，肯定是没有问题的，因为实际操作中一旦到达这个状态就结束了，它不会自己转移到自己，那我们就可以直接$dp$了

状态转移

根据概率的概念，一次事件是一次试验可能结果的子集，那么一个事件$s$的概率是

$p(s) = \frac{|s|}{|S|}$

也就是说我们对当前状态进行一次操作会产生有限种结果，每种结果有一种概率(这些结果概率和必为$1$)，然后再根据

$E(X) = \sum_{s \in S} p(s) \times E(s)$

求出期望就可以了，这里其实也告诉我们： 我们设计$dp$状态时要把实际操作中的结束状态设为$dp$的初始状态，因为在$dp$中，我们当前状态需要由实际操作中从这种状态操作一次会产生的所有子状态转移，也就是说，我们要算当前状态的$dp$值，我们需要的是实际操作后的状态的$dp$值，所有我们$dp$的过程和实际操作的过程是相反的

Zth's Blog

Namomo 每日一题div1 675 吃蛋糕并浅谈期望dp

题目

题意