BZOJ4318 概率期望dp

Posted on | In , ,

给定一个长度为n的01串，第i个位置有ai的概率为1，最终得分为01串中所有连在一起1的长度的立方和，求得分的期望

题目链接

题解

  • 一开始不知道由i到i+1怎么转移，因为前i个连续的1的个数不确定，但我们可以算前i个连续1的期望个数，问题便解决了。
  • 定义$f_i$: 前i位连续1的期望个数，考虑第i-1到第i位的转移
  • 若第i位是1，则多出的贡献为$(f_{i-1}+1)^3-f_{i-1}^3=3f_{i-1}^2+3f_{i-1}+1$，则前 $i$ 位的分数期望为$dp_i=dp_{i-1}+(3f_{i-1}^2+3f_{i-1}+1)·p_i$( $p_i$ 为 $1$ 的概率)
  • 分别维护 $ f_i$ 和 $f_i^2$ ，其中$f_i=(f_{i-1}+1)·p_i$，$f_i$可以通过期望的线性性质推出，$f_(i+1)^2=f_i^2+2f_i+1$，将 $i$ 替换为 $(i-1)$ 即可算出 $f_i$。
  • 注意期望的平方和平方期望的区别。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
const int INF=1e9+7;

int n;
double ans[maxn];
double p1[maxn], p2[maxn], x[maxn];

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf", &x[i]);
        p1[i]=(p1[i-1]+1)*x[i];
        p2[i]=(p2[i-1]+2*p1[i-1]+1)*x[i];
        ans[i]=x[i]*(3*p2[i-1]+3*p1[i-1]+1)+ans[i-1];
    }
    printf("%.1f\n", ans[n]);
}