291312a_tải nhạc

291312a_tải nhạc一个序列长度是L,每个位置取1的概率是p,取0的概率是1-p

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

一个序列长度是L,每个位置取1的概率是p,取0的概率是1 – p。连续的n个1的得分是1 + 2 + …… + n。求分数的期望。

http://www.bnuoj.com/bnuoj/problem_show.php?pid=29140

dp[i][j]为长度是i的序列,后j个都是1的概率,f[i]是长度为i的序列的得分。(EX = ∑xi * pi, f[i]就是xi * pi)ans = ∑f[i]

dp[0][0] = 1;                                                    f[0] = 0;

dp[1][0] = 1 – p, dp[1][i] = p;                            f[1] = p;

我们考虑L = 3的情况, 可能的序列为:

000

001

010

011

100

101

110

111

考虑第1为是1,只有后面4个序列的第1位是1对答案的贡献为:p * (1 – p) * (1 – p) * 1 + p * (1 – p) * p * 1 + p * p * (1 – p) * 1 + p * p * p * 1 = p,而f[1]同样为p。

 第2位是1的序列对答案的贡献为:(1 – p) * p * (1 – p) * 1 + (1 – p) * p * p * 1 + p * p * (1 – p) * 2 + p * p * p * 2 = p + p * p。

 第3位是1的序列对答案的贡献为:(1 – p) * (1 – p) * p * 1 + (1 – p) * p * p * 2 + p * (1 – p)  * p * 1 + p * p * p * 3 = p + p * p + p * p * p。对于序列001和101来说,在第3位得分都是1,(1 – p) * (1 – p) * p * 1 + p * (1 – p)  * p * 1 = (1 – p) * p。在不考虑第3位 情况下,00和10构成dp[2][0],由于它们的第3位都是1,所以其概率为dp[2][0] * p。

由此可以推出dp[2][0] = 1 – p。并且可以依次推出dp[i][0] = 1 – p。

于是就可以这样做~~~

   for(int i=1; i<=L; i++){
            dp[i][0] = 1.0 - p;
            f[i] = 0;
            for(int j=1; j<=i; j++){
                dp[i][j] = dp[i - 1][j - 1] * p;
                f[i] += dp[i][j] * j;
            }
            ans += f[i];
        }

Jetbrains全家桶1年46,售后保障稳定

但是这样是会TLE的,有<=1000组数据,L<=1000。复杂度为O(L^2),所以1000 * 1000 * 1000 = ……     = =#。。。。QAQ

我们先手算几个数据:

f[0] = 0;

f[1] = p;

f[2] = p + p * p;

f[3] = p + p * p + p * p * p;

.

.

.

发现f[i] = ∑p^k, k = 1, 2, …, i      (⊙v⊙)…

于是,

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 10;
double dp[maxn][maxn], f[maxn];
int L, T;
double p, ans;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%lf", &L, &p);
        ans = 0.0;
        double tmp = p;
        for(int i=0; i<L; i++){
            ans += (L - i) * tmp;
            tmp *= p;
        }
//        dp[0][0] = 1.0;
//        f[0] = 0;
//        for(int i=1; i<=L; i++){
//            dp[i][0] = 1.0 - p;
//            f[i] = 0;
//            for(int j=1; j<=i; j++){
//                dp[i][j] = dp[i - 1][j - 1] * p;
//                f[i] += dp[i][j] * j;
//            }
//            ans += f[i];
//        }
        printf("%lf\n", ans);
    }
    return 0;
}

over~ (>^ω^<)喵~

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:http://www.javaforall.cn/234872.html原文链接:http://www.javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • idea没有生成target文件夹_整体打包项目

    idea没有生成target文件夹_整体打包项目**问题**:打包的文件夹不知道怎么了被我不小心点到设置不显示了,只有src目录但是进入项目的文件夹路径下查看确又是存在的解决:如下图,把showExcludedFiles给勾选上…

  • clion 激活码【2021.10最新】[通俗易懂]

    (clion 激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • cnpm安装和使用[通俗易懂]

    cnpm安装和使用[通俗易懂]在已经安装node.js基础上,利用npm来安装cnpm。cnpm是利用淘宝镜像来安装依赖包!优点:会比npm安装来的速度更快  操作:1、全局安装cnpm,打开cmd输入:npmi-gcnpm 2、验证是否安装成功,可以通过查看版本:cnpmversion当出现如下版本号,表示安装成功 …

    2022年10月10日
  • 基于 mysql时序_时序数据库简介

    基于 mysql时序_时序数据库简介时间序列数据库简称时序数据库(TimeSeriesDatabase),用于处理带时间标签(按照时间的顺序变化,即时间序列化)的数据,带时间标签的数据也称为时间序列数据。时序数据的几个特点1.基本上都是插入,没有更新的需求。2.数据基本上都有时间属性,随着时间的推移不断产生新的数据。3.数据量大,每秒钟需要写入成千万上亿条数据业务方常见需求1.获取最新状态,查询最近的数据(例如传感器最新…

  • npm 安装yarn

    Yarn是Facebook最近发布的一款依赖包安装工具。Yarn是一个新的快速安全可信赖的可以替代NPM的依赖管理工具快速安装//在NPM中安装npminstall-gyarnMacOS在Mac上安装比较方便,使用初始化脚本即可 1 curl-o–Lhttps://yarnpkg.com/install.sh|ba…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号