P1654 OSU!

    • 596通过
    • 790提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    原 《产品排序》 参见P2577

    题目描述

    osu 是一款群众喜闻乐见的休闲软件。

    我们可以把osu的规则简化与改编成以下的样子:

    一共有n次操作,每次操作只有成功与失败之分,成功对应1,失败对应0,n次操作对应为1个长度为n的01串。在这个串中连续的 $X$ 个 $1$ 可以贡献 $X^3$ 的分数,这x个1不能被其他连续的1所包含(也就是极长的一串1,具体见样例解释)

    现在给出n,以及每个操作的成功率,请你输出期望分数,输出四舍五入后保留1位小数。

    输入输出格式

    输入格式:

    第一行有一个正整数n,表示操作个数。接下去n行每行有一个[0,1]之间的实数,表示每个操作的成功率。

    输出格式:

    只有一个实数,表示答案。答案四舍五入后保留1位小数。

    输入输出样例

    输入样例#1: 复制
    3 
    0.5 
    0.5 
    0.5
    输出样例#1: 复制
    6.0

    说明

    【样例说明】

    000分数为0,001分数为1,010分数为1,100分数为1,101分数为2,110分数为8,011分数为8,111分数为27,总和为48,期望为48/8=6.0

    N<=100000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。