<题解>P1654 OSU!

X_i为到i位置的得分,L_{i,j}i位置结尾长度为jJ_{i}表示i位置连续为1的长度,S_i表示i位置判定成功

考虑x+1位为1,算出了E(X_x)
E(X_{x+1}) = E(X_x) + P(S_{x+1})\cdot(\sum_{i=0}^x P(L_{x,i})((i+1)^3-i^3))

化简一下
E(X_{x+1}) = E(X_x) + P(S_{x+1})\cdot(\sum_{i=0}^x P(L_{x,i})(3i^2+3i+1))

然后把3i^2+3^i+1那个括号拆一下,拿出一块:
3\sum_{i=0}^xP(L_{x,i})\cdot i^2 = 3E(J_x)
再带回原式:
E(X_{x+1}) = E(X_x) + P(S_{x+1})\cdot(3E(J_x^2)+3E(J_x)+1)

然后再推两个东西:
E(J_{x+1}) = P(S_{x+1})\cdot(E(J_{x}) + \sum_{i=0}^xP(L_{x,i}))=P(S_{x+1})\cdot(E(J_x)+1)
\begin{aligned} E(J_{x+1}^2) &= P(S_i)\cdot(E(J_x^2)+\sum_{i=0}^xP(L_{x,i})((i+1)^2-i^2)) \\ &=P(S_i)\cdot(E(J_x^2) + \sum_{i=0}^xP(L_{x,i})(2i+1))\\ &=P(S_i)\cdot(E(J_x^2) + 2E(J_{x}) + 1) \end{aligned}

#include <cstdio>

int    n;
double e1, e2, e, p;

int main(void)
{
    scanf("%d", &n);
    while (n--)
    {
        scanf("%lf", &p);
        e = e + p * (3*e2 + 3 * e1 + 1);
        e2 = p * (e2 + 2 * e1 + 1);
        e1 = p * (e1 + 1);
    }
    printf("%.1lf", e);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注