Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. C++
  3. 正文

CUP 4367: Tyvj1952 Easy BZOJ

2018年08月16日 1503点热度 0人点赞 0条评论

内容纲要

题解

由于给定序列,$o$的概率一定是1,$x$的概率一定是0.
$?$的期望实际上是0.5
我们要求的是$E_{x^2}$,令$dp_i$代表到第i位时$E_{x^2i}$,$l_i$为到达$i$位置时的期望长度。根据上述条件,$o$时$l_i = l_{i-1} + 1$,$x$时$l_i = 0$,而$x$的时候$l_i = 0.5 \times (l_{i-1} + 1)$

根据$l$,观察$E_i - E_{i-1}$,可以发现$x^2 - (x - 1)^2 = 2x + 1$
因此$dp_i = dp_{i - 1} + 2 \times l_{i - 1} + 1$
$dp_n$为答案

AC代码

#include <iostream>
#include <iomanip>
using namespace std;
const int maxn = 3e5+6;
long double dp[maxn],l[maxn];
int main()
{
    int n;
    string s;
    cin >> n >> s;
    s = " " + s;
    for(int i = 1;i<=n;++i)
    {
        if(s[i] == 'o') {
            dp[i] = dp[i - 1] + l[i - 1] * 2 + 1;
            l[i] = l[i - 1] + 1;
        }
        else if(s[i] == 'x') {
            dp[i] = dp[i - 1];
            l[i] = 0;
        }
        else {
            dp[i] = dp[i - 1] + l[i - 1] + 0.5;
            l[i] = l[i - 1] / 2 + 0.5;
        }
    }
    cout << setiosflags(ios::fixed) << setprecision(4);
    cout << dp[n] << '\n';
}

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: C++ 动态规划
最后更新:2018年08月16日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
GitHub Apache JavaScript Java php C C++ hustoj
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 15,389
  • 5,591
  • 180
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?