P1654 OSU!
题目大意
有 n 个操作,每个操作只有成功或失败两种状态,如果有一段连续的长度为 x 的成功操作(左右两端都是失败的),则会获得 x3 的分数,现在给定每个操作成功概率 pi,求期望分数。
数据范围:1≤n≤105。
题解
考察期望 Ei(x) 在第 i 次点击成功后相较于 Ei−1(x) 的增加量。
即若 Ei−1(x) 恰好成功点击 x 次,则 E((x+1)3−x3)=E(3x2+3x+1)=3E(x2)+3E(x)+1。
这告诉我们,想要维护三阶期望需要先维护一阶和二阶期望,考虑转移:Ei(x)=pi×(Ei−1(x)+1),Ei(x2)=pi×(Ei−1(x2)+2Ei−1(x)+1),Ei(ans)=Ei−1(ans)+pi×(3Ei−1(x2)+3Ei−1(x)+1)。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef double DB;
const int N = 1e5+10;
int n;
DB p[N] , e1[N] , e2[N];
int main() {
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i ++)
scanf("%lf" , &p[i]);
DB ans = 0;
for(int i = 1 ; i <= n ; i ++) {
e1[i] = p[i]*(e1[i-1]+1);
e2[i] = p[i]*(e2[i-1]+e1[i-1]*2+1);
ans = ans + p[i]*(e2[i-1]*3+e1[i-1]*3+1);
}
printf("%.1lf\n" , ans);
return 0;
}