P1654 OSU!

P1654 OSU!

Meaning

共有 $n$ 次操作。每次操作有 $p_i$ 的概率在当前位置填 1，否则填 0。

一串极长全 1 子串 $s$ 的贡献为 $|s|^3$，求期望贡献。

Sol

考虑设计 dp 状态，令 $dp_{i,0}$ 表示以 $i$ 结尾的极长全 1 子串的三次方贡献，同理令得 $dp_{i,1},dp_{i,2}$ 分别表示以 $i$ 为结尾的极长全 1 子串的二次方贡献和一次方贡献。注意到我们的设定使得以 $i$ 为结尾前面全为 1 的子串。考虑到期望线性性，那么显然有转移方程为

$dp_{i,0} = p_{i} \times (dp_{i-1,0} + 3 \times dp_{i-1,1} + 3 \times dp_{i-1,2} + 1) \\ dp_{i,1} = p_{i} \times (dp_{i-1,1} + 2 \times dp_{i-1,2} + 1) \\ dp_{i,2} = p_{i} \times (dp_{i-1,2} + 1)$

最后考虑如何统计答案，由于我们所设计的状态保证了以 $i$ 为结尾的全 1 子串会产生贡献，当且仅当之前所有位置全为 1，而后位置为 0。那么显然答案为 $dp_{n,0} + \sum_{i=1}^{n - 1} (1 - p_{i+1}) \times dp_{i,0}$。

Detail

1. 对于期望 dp 的状态设计不够敏感；
2. 容易在统计答案时忽略状态本身的意义。

Code

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 1e5 + 1e1;
const lint INF = 1e18 + 1e9;

double f[MAXN], g[MAXN], h[MAXN], p[MAXN], Ans;
int n;

int main(void) {

    n = readint;
    for (int i = 1; i <= n; i ++) scanf("%lf", &p[i]);
    for (int i = 1; i <= n; i ++) {
        f[i] = p[i] * (f[i - 1] + 1.0);
        g[i] = p[i] * (g[i - 1] + 2.0 * f[i - 1] + 1.0);
        h[i] = p[i] * (h[i - 1] + 3.0 * g[i - 1] + 3.0 * f[i - 1] + 1.0);
    }
    for (int i = 1; i < n; i ++) Ans += (1.0 - p[i + 1]) * h[i];
    printf("%.1lf\n", Ans + h[n]);

    return 0;
}