CF235B Let's Play Osu! 期望DP

貌似是一道很裸的期望(DP)。直接说思路:
(f[i])表示到(i)位置时的期望分数,但是只有(f[i])的话我们发现是无法转移的,我们还需要知道到(i)位置时的期望连续长度,于是我们再设一个(g[i])表示到(i)位置时的期望连续长度,(g[i])可以(O(1))转移,转移方程为:(g[i]=(g[i-1]+1)p[i])(p[i])(i)位置成功的概率。进而我们来yy(f[i])的转移:
1.(i)位置为“O”,设(x)(i)位置之前的连续的“O”的个数,则新的收益为((x+1)^2),即(x^2+2x+1),相差一个(2x+1),所以贡献为(p[i](f[i-1]+2g[i-1]+1))
2.(i)位置为“X”,贡献为(f[i-1])
综上所述,(f[i]=f[i-1](1-p[i])+(f[i-1]+2g[i-1]+1)p[i])
这样的话代码就很显然了:

#include <bits/stdc++.h>
using namespace std;
int n;
double p[100000+5], f[100000+5], g[100000+5];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
    for(int i = 1; i <= n; ++i) g[i] = (g[i-1]+1)*p[i], f[i] = f[i-1]*(1-p[i])+(f[i-1]+2*g[i-1]+1)*p[i];
    printf("%.8lf
", f[n]);
    return 0;
}
原文地址:https://www.cnblogs.com/dummyummy/p/9885263.html