题解 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的转移：

故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!