CF235B Let's Play Osu!

· · 题解

不会概率期望的线性性质怎么办？想不出题解中的神奇dp怎么办？

就用普通的概率dp做法即可，无脑推式子。

我们令d(i)表示前i个的期望分值。d(0)=0,规定d(-1)=0。（方便起见）显然有：

d(i)=\sum_{j=0}^i [d(j-1)+(i-j)^2](1-p_j)\prod_{k=j+1}^ip_k

虽然长得恶心，但不难理解。j就是来枚举“失败”的位置（可以是0），所以要乘上 (1-p_j)。j之后的必定都成功，所以有了乘积式\prod_{k=j+1}^ip_k。

之后怎么办？那个完全平方让人难以下手。所以把它拆了，同时将i项提到前面去。

d(i)= \sum_{j=0}^i[d(j-1)+j^2](1-p_j)\prod_{k=j+1}^ip_k-2i\sum_{j=0}^ij(1-p_j)\prod_{k=j+1}^ip_k+i^2\sum_{j=0}^i(1-p_j)\prod_{k=j+1}^ip_k

虽然还是恶心，但我们令：

A_i=\sum_{j=0}^i[d(j-1)+j^2](1-p_j)\prod_{k=j+1}^ip_k\\ B_i=\sum_{j=0}^ij(1-p_j)\prod_{k=j+1}^ip_k\\ C_i=\sum_{j=0}^i(1-p_j)\prod_{k=j+1}^ip_k \end{aligned}

（此时有d(i)=A_i-2iB_i+i^2C_i）

可以发现，ABC都可以递推出来。

A_i=p_iA_{i-1}+[d(i-1)+i^2](1-p_i)\\ B_i=p_iB_{i-1}+i(1-p_i)\\ C_i=p_iC_{i-1}+1-p_i \end{aligned}

边际条件？可以看出A_0=B_0=0,C_0=1。（能够证明C恒为1）

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define F(i,a,b) for(int i=a;i<=b;++i)
const int maxn=1e5+5;
int n;
double p[maxn],d[maxn];
int main()
{
    scanf("%d",&n);
    F(i,1,n) scanf("%lf",&p[i]);
    double a=0,b=0;
    F(i,1,n)
    {
        a=p[i]*a+(d[i-1]+(double)i*i)*(1-p[i]);
        b=p[i]*b+i*(1-p[i]);
        d[i]=a-2*b*i+(double)i*i;
    }
    printf("%.9lf",d[n]);
    return 0;
}

（思维难度并不高）