P1654 OSU!

放在前面：这是一道期望dp大水题，属于那种看题解一看就会，自己写一写就废的那种。

一. 思路

（不想看我前面唠叨就直接看代码吧）

1. 确定状态转移方程

did_i：ii 次操作后得的分数。则 E(di)E(d_i)：ii 次操作后期望的的分数。

第 ii 轮后，得分发生了怎样的变化了呢？我们先只看从最近一次失败后算起的成功的一段，ii 轮前得分是 x3x^3，如果低 ii 次成功，ii 轮后是 (x+1)3=x3+3x2+3x+1(x+1)^3=x^3+3x^2+3x+1，反之是 00。变化了 3x2+3x+13x^2+3x+1。再加上之前的得分 di−1d_{i-1}。

综上所述，已知成败情况的状转方程：

xi={0(fail)xi−1+1(success)x_i=\begin{cases}0&(fail)\\x_{i-1}+1&(success)\end{cases}

x2i={0(fail)x2i−1+2xi−1+1(success){x^2}_i=\begin{cases}0&(fail)\\{x^2}_{i-1}+2x_{i-1}+1&(success)\end{cases}

di=di−1+{0(fail)3x2i−1+3xi−1+1(success)d_i=d_{i-1}+\begin{cases}0&(fail)\\3{x^2}_{i-1}+3x_{i-1}+1&(success)\end{cases}

设第 ii 次成功的几率为 probiprob_i。

综上所述，期望状转方程：

E(x)i=probi×(E(x)i−1+1)+(1−probi)×0=probi×(E(x)i−1+1)E(x2)i=probi×(E(x2)i−1+2E(x)i−1+1)+(1−probi)×0=probi×(E(x2)i−1+2E(x)i−1+1)E(d)i=E(d)i−1+probi×(3E(x2)i−1+3E(x)i−1+1)+(1−probi)×0=E(d)i−1+probi×(3E(x2)i−1+3E(x)i−1+1)\begin{aligned} E(x)_i&=prob_i\times (E(x)_{i-1}+1)+(1-prob_i)\times 0 \\ &=prob_i\times (E(x)_{i-1}+1) \\ E({x^2})_i&=prob_i\times(E({x^2})_{i-1}+2E(x)_{i-1}+1)+(1-prob_i)\times 0 \\ &=prob_i\times(E({x^2})_{i-1}+2E(x)_{i-1}+1) \\ E(d)_i&=E(d)_{i-1}+prob_i\times(3E({x^2})_{i-1}+3E(x)_{i-1}+1)+(1-prob_i)\times 0 \\ &=E(d)_{i-1}+prob_i\times(3E({x^2})_{i-1}+3E(x)_{i-1}+1) \\ \end{aligned}

2. 坑点

  • E(a2)≠E(a)2E(a^2)\ne E(a)^2

    也就是说，不能将状转方程中的 E(x2)E(x^2) 用 E(x)E(x) 表示。

  • d≠x3d\ne x^3

    dd 比 x3x^3 还额外需要考虑之前的累计得分，也就是 did_i 要加上 di−1d_{i-1}。

  • E(d)E(d)、E(x2)E(x^2) 和 E(x)E(x) 更新的顺序

    如果你不开数组，就要格外注意这一点。dd 的期望状转方程中用到 E(d)E(d)、 E(x2)E(x^2) 和 E(x)E(x)；x2x^2 的用到 E(x2)E(x^2) 和 E(x)E(x)；xx 的只用到自己，并且用的都是上一阶段的。所以先刷新 E(d)E(d)，再刷新 E(x2)E(x^2)，最后 E(x)E(x)。

二. 代码

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
int n; double prob, d, x2, x;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%lf", &prob);
        d = d + prob * (3 * x2 + 3 * x + 1);
        x2 = prob * (x2 + 2 * x + 1);
        x = prob * (x + 1);
    }
    printf("%.1lf", d);
}