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,转载请注明出处:https://javaforall.cn/234872.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 计算机考研数据库题库及答案_数据结构历年考研真题

    计算机考研数据库题库及答案_数据结构历年考研真题在数据库的三级模式结构中,描述数据库中全体数据的全局逻辑结构和特征的是()。A.充分必要条件B.必要条件C.充分条件D.既不充分也不必要条件。A.需求分析阶段B.概念设计阶段C.逻辑设计阶段D.物理设计阶段。在关系模式R(U,F)中,Y∈XF+是X→Y是否成立的()。A.数据库系统B.文件系统C.人工管理D.数据项管理。A.网络系统B.数据库系统C.操作系统D.数据库。A.外模式B.内模式C.存储模式D.模式。…

    2022年10月26日
  • Apache Shiro框架简介[通俗易懂]

    Apache Shiro框架简介[通俗易懂]shiro是什么我们在做web应用时总会需要做登录等身份认证。一般情况下我们都是自己写加密(例如MD5加密)和帐号密码对比。一般做法通过表单提交用户名及密码达到认证目的。权限方面的管理则通过一般的判断。比如哪个账户可以看到哪些模块,可以进行哪些操作。而shiro就是一个封装以上需求操作的开源框架。它能帮助我们更好更方便的做好web应用的安全管理。而不需

  • js有几种数据类型,基本数据类型有哪些_js中简单数据类型

    js有几种数据类型,基本数据类型有哪些_js中简单数据类型js中数据类型分为原始数据类型与引用数据类型原始数据类型:number//数值类型:值只能为数字vara=12string//字符串类型:值都是以引号包裹的vara=’你好’boolean//布尔类型:值只存在真假vara=truevara=falsenull//空类型vara=nullundefined//未定义类型:定义了变量a,但是没有a赋值varaconsole.log(a

  • 如何查看tomcat版本_tomcat修改端口号

    如何查看tomcat版本_tomcat修改端口号一、通过tomcat版本文件查看  找到tomcat目录,进入”xxx/tomcat/bin”目录,执行”shversion.sh”。如果没有设置JAVA_HOME和JRE_HOME环境变量则会报如下错误:[jieyu.ljy@tripco011182064160.na62xxx/tomcat/bin]$shversion.shNeithertheJAVA_HOMEn…

  • Redis学习笔记–Redis数据过期策略详解

    Redis学习笔记–Redis数据过期策略详解

  • docker导入镜像命令_docker怎么删除镜像

    docker导入镜像命令_docker怎么删除镜像由于工作需要,要一次性导出机器上全部的镜像。

发表回复

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

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