CF235B Let's Play Osu!解题报告

解题报告

CF235B Let's Play Osu!解题报告：

更好的阅读体验

题意

题意：给定一个序列，每一个位置$i$为$1$的几率为$p_i$，长度为$k$的极长$1$序列的贡献为$k^2$，求期望贡献。
数据范围：$1\leqslant n\leqslant 10^5$

分析

很容易发现这是一道概率dp。

我们考虑以$i$为结尾的极长$1$序列长度为$len_i$，则可以分两种情况讨论$len$的转移：

1. $i$位置为$1$，几率为$p_i$，期望长度为$len_{i-1}+1$；
2. $i$位置为$0$，几率为$1-p_i$，期望长度为$0$。

故$len_i=(len_{i-1}+1)\times p_i+0\times(1-p_i)$

我们求得了位置$i$的期望长度为$len_i$后，可以考虑转移答案$ans$：

首先，在这个极长$1$序列之前的期望贡献显然不需要考虑，我们只需要考虑以$i$结尾的极长$1$序列：
1. 若当前位置为$1$，概率为$p_i$，则在$i-1$位置时，期望长度为$len_{i-1}$，则期望贡献为$len_{i-1}^2$；在$i$位置时，期望长度为$len_{i-1}+1$，则期望贡献为$(len_{i-1}+1)^2=len_{i-1}^2+2len_{i-1}+1$。这两个式子相减则为答案：$len_{i-1}^2+2len_{i-1}+1-len_{i-1}^2=2len_{i-1}+1$；
2. 若当前位置为$0$，概率为$1-p_i$，则无以$i$结尾的极长$1$序列，无贡献。

故$ans_i=ans_{i-1}+(2*len_{i-1}+1)\times p_i+0\times(1-p_i)$

代码

记得保留$15$位小数。

#include<stdio.h>
const int maxn=100005;
int i,j,k,m,n;
double len[maxn],ans[maxn];
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        double p;
        scanf("%lf",&p);
        len[i]=(len[i-1]+1.0)*p+0.0*(1-p);
        ans[i]=ans[i-1]+(2.0*len[i-1]+1.0)*p+0.0*(1-p);
    }
    printf("%.15lf",ans[n]);
    return 0;
}

后话

本题弱化版：P1365 WJMZBMR打osu! / Easy
本题扩展版：P1654 OSU!