洛谷P1365 期望dp
2024-10-21 06:27:32
题目描述
一个o/x序列的得分为其中每个o的极大连续子段长度的平方和,比如ooxxxxooooxxx,分数就是
\(2 \times 2 + 4 \times 4 = 4 +16=20。\)
现给定一个o/x/?序列,?代表着有\(\frac 12\)的几率是o,\(\frac 12\)的几率是x,求序列的期望得分
\(n\le 3e5 + 5\)
正解:O(n)期望dp
我们假设\(f_i\)代表前i个数的期望答案,这时推导时我们发现,需要用到最后一段连续o的个数,但是迫于数据范围,这个值不能直接算,也不能枚举。这个时候我们该怎样得到这样一个值呢?这道题给了我们一个全新的思路。
对于每一位p,计算1~p - 1位连续'o'个数的期望,再用期望值计算:
\(s_p\) == 'x':E(p) = 0
\(s_p\) == 'o':E(p) = E(p - 1) + 1
\(s_p\) == '?':E(p) = \(\frac {(E(p - 1) + 1) + 0}{2}\) (E(p - 1) + 1是'?'为'o'的收益,0是'?'为'x'的收益)
将极大段的'o'拆分可得,\({(p + 1)}^2 - p^2 = 2p + 1\),对于每一个值为'o'的位置,\(f_p = f_{p - 1} + 2s_{p - 1} + 1\),对于每一个值为'?'的位置,\(f_p = f_{p - 1} + \frac {2s_{p - 1} + 1}2\)
一句话概括:当前位收益E(2p + 1) = 2E(p) + 1
Code
#include<bits/stdc++.h>
using namespace std;
string s;
double f[300005];
int n;
int main()
{
double len = 0;
cin>>n;
cin>>s;
f[0] = 0;
for(int i = 0;i < s.length();i++)
{
if(s[i] == 'o')
{
f[i + 1] = f[i] + len * 2 + 1;
len++;
}
if(s[i] == 'x')
{
f[i + 1] = f[i];
len = 0;
}
if(s[i] == '?')
{
f[i + 1] = f[i] + len + 0.5;
len = (len + 1) / 2;
}
}
cout<<fixed<<setprecision(4)<<f[n];
return 0;
}
最新文章
- Servlet技术(使用myeclipse)
- Flyweight(享元)--对象结构型模式
- HTTP 状态代码表示什么意思?
- web文档在线阅览
- XStream-----把JavaBean转换为xml的工具
- Ubuntu 更新源
- 【转载】Android异步处理系列文章
- Struts2学习笔记--Struts例子及开发流程
- Link all references for a local rename (does not change references in other files)
- 命令行运行命令时报错You don&;#39;t have write permissions for the /Library/***
- ldap数据库--ODSEE--复制协议
- ASP.NET根据当前时间获取,本周,本月,本季度等时间段
- 一个&#39;&;&#39;引起md5签名不一致问题
- 怎样从外网访问内网Tornado
- Python_函数的镶嵌和作用域链_26
- nginx https 配置样例
- 解决java网络编程IPv6问题
- repositoryItemButtonEdit ButtonClick没有反应的原因
- Spring Boot -01- 快速入门篇(图文教程)
- edge中断分析