洛谷 P1654 OSU!

思路

考虑 \(DP\) 转移，设 \(F[i]\) 表示长度为 \(i\) 序列的期望分数。

得到如下转移：

\(F[i]=(F[i-1]-A[i-1]+A[i])p_i+F[i-1](1-p_i)\)

其中 \(A[i]\) 的意义是：以 \(i\) 位 \(1\) 结尾极长连续段的立方贡献的期望分数。

再设 \(B[i]\) 为以 \(i\) 位 \(1\) 结尾极长连续段的平方贡献的期望分数，\(C[i]\) 为以 \(i\) 位 \(1\) 结尾极长连续段贡献的期望分数。

可以发现：\(A[i]\) 可以由 \(B[i]\) 和 \(C[i]\) 转移得到：\(A[i]=A[i-1]+3B[i-1]+3C[i-1]+1\)

上式是因为：\((x+1)^3=x^3+3x^2+3x+1\)

同理: \(B[i]=B[i-1]+2A[i-1]+1, C[i]=C[i-1]+1\)

于是：\(F[i] = F[i - 1] + (3B[i - 1] + 3C[i - 1] + 1)p_i\)

#include <bits/stdc++.h>
const int Maxn = 1e5 + 5;
double a[Maxn], b[Maxn], f[Maxn], p[Maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &p[i]);
    a[1] = b[1] = f[1] = p[1];
    for (int i = 2; i <= n; i++)
    {
        a[i] = (a[i - 1] + 1) * p[i];
        b[i] = (b[i - 1] + 2 * a[i - 1] + 1) * p[i];
        f[i] = f[i - 1] + (3 * b[i - 1] + 3 * a[i - 1] + 1) * p[i];
    }
    printf("%.1lf", f[n]);
    return 0;
}