LP1654 OSU! [期望]
Solution
设状态 $f_i$ 表示以 $i$ 结尾的段的期望长度的立方。则如果 $i$ 为 $1$,对这个长度为 $x$ 的段的答案贡献为 $3x^2+3x+1$,如果 $i$ 为 $0$ 则不产生贡献。根据期望的线性性质,我们需要计算 $x^2$ 和 $x$ 的期望。
状态 $g_i$ 表示期望长度的平方,状态 $h_i$ 表示期望长度,则 $f_i=p_i(f_{i-1}+3g_{i-1}+3h_{i-1}+1)$。
同理有 $g_i=p_i(2h_{i-1}+1)$,$h_i=p_i(h_{i-1}+1)$。
将 $f_i$ 的方程式稍加改动变为 $f_i=p_i(f_{i-1}+3g_{i-1}+3h_{i-1}+1)+(1-p_i)f_{i-1}$ 即变成答案。那么我们发现 $f_i$ 的含义发生了变动。考虑如果以 $i-1$ 结尾的期望长度为 $x$,那么产生的贡献的期望也就是 $3E(x^2)+3E(x)+1$,跟 $f_i$ 的含义其实是无关的。我们初始的方程只是忽略了 $i$ 可以为 $0$ 的情况,而对于 $g_i, h_i$ 两个状态我们必须忽略 $i$ 可以为 $0$ 的情况,否则无法为 $f_i$ 提供转移。
其它感觉都还好理解吧。
Code
// Code by ajcxsu
// Problem: osu
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
double f[N], f2[N], ans;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.setf(ios::fixed), cout<<setprecision(1);
int n;
cin>>n;
double p;
for(int i=1;i<=n;i++) {
cin>>p;
f[i]=(f[i-1]+1)*p;
f2[i]=(f2[i-1]+2*f[i-1]+1)*p;
ans+=(3*f2[i-1]+3*f[i-1]+1)*p;
}
cout<<ans<<endl;
return 0;
}