

BZOJ4318 OSU!

题意

给定一个序列，每个位置为 $\texttt{o}$ 的几率为 $p_i$ ，为 $\texttt{x}$ 的几率为 $1 - p_i$ 。对于一个 $\texttt{ox}$ 序列，连续 $x$ 长度的 $\texttt{o}$ 会得到 $x^3$ 的收益，问最终得到的 $\texttt{ox}$ 序列的期望收益是多少？

题解

这题和20181106的考试题很像（ $x^2$ 变成了$x^3$），属于升级版，和BZOJ3450有一定联系。
可以将题目转化一下，变成以每个点为右端点的区间长度的期望的立方的和。
设 $g[i]$ 为以 $i$ 位置为右端点的的期望的立方的和。
由于此时变为区间的立方，所以在转移 $g$ 时不能简单的由以 $i$ 为右端点的长度的期望转移。
（如果问题改为收益为 $x^2$ 可以，因为 $(x+1)^2-x^2=x\times 2-1$ ）
考虑 $g[i]$ 如何由 $g[i-1]$ 转移而来。
我们发现如果 $i-1$ 产生收益的期望 $g[i-1]=x^3$ ，那么 $i$ 可以产生的收益的期望为 $((x+1)^3 - x^3) \times p_i$ （其中 $p_i$ 为 $i$ 产生 $\texttt{o}$ 的概率）。
然后将括号中的式子用立方差公式处理一下：
$$g[i]=(x+1-x)\times [(x+1)^2 + x\cdot (x+1) + x^2]=3x^2+3x+1$$
相当于只需要知道区间长度期望与区间长度立方的期望就行了。
于是设 $f[i][j]$ 表示，以第 $i$ 个位置结尾的区间长度的 $i$ 次方的期望。
有转移方程：
$f[1][i] = f[1][i-1]\times p_i$
$f[2][i] = (2 * f[2][i-1] - 1) \times p_i$ （这个在之前提到了）
于是可以得到 $g$ 的转移式:
$$g[i]=(3\times f[2][i - 1] + 3\times f[1][i - 1] + 1) \times p_i$$
最终的答案就是 $\sum_{i=1}^{N}g[i]$ ，在程序中可以将 $g$ 记成前缀和答案就是 $g[N]$

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MAX_N 100007
#define reg register
typedef long long ll;

int N;
double p[MAX_N], f[2][MAX_N], g[MAX_N];

template <typename _T> inline void read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while (c < '0' || '9' < c) {
        if (c == '-') y = -1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
}

inline void dp () {
    for (int i = 1; i <= N; ++i) 
        f[0][i] = (f[0][i - 1] + 1) * p[i];
    for (int i = 1; i <= N; ++i)
        f[1][i] = (f[1][i - 1] + 2 * f[0][i - 1] + 1.0) * p[i];
    for (int i = 1; i <= N; ++i) 
        g[i] = g[i - 1] + (3.0 * f[1][i - 1] + 3.0 * f[0][i - 1] + 1.0) * p[i];
    printf("%.1lf\n", g[N]);
}

int main () {
    read(N);
    for (int i = 1; i <= N; ++i)
        scanf("%lf", p + i);
    dp();
    return 0;
}