LP1654 OSU! [期望]

Author Avatar
空気浮遊 2019年02月16日
  • 在其它设备中阅读本文章
  • 期望
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

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;
}

本文链接:https://pst.iorinn.moe/archives/sol-luogu-1654.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material