bzoj 4318 OSU!
2024-10-14 03:21:45
期望dp。
考虑问题的简化版:一个数列有n个数,每位有pi的概率为1,否则为0。求以每一位结尾的全为1的后缀长度的期望。
递推就好了。
l1[i]=(l1[i-1]+1)*p[i]+0*(1-p[i]);
再考虑一发:一个数列有n个数,每位有pi的概率为1,否则为0。求以每一位结尾的全为1的后缀长度的平方的期望。
平方的期望显然不等于期望的平方。但是平方的期望也是可以递推的。
l2[i]=(l2[i-1]+2*l1[i-1]+1)*p[i]+0*(1-p[i]);
l3立方同理。
再来考虑问题,第i位的答案与第i-1位的答案的差只与后缀全为1的串有关,所以我们只需要计算前一位后缀全为1的串后再加一个1的值减掉前一位的值就行了。
ans[i]=(ans[i-1]+l3[i]/p[i]-l3[i-1])*p[i]+ans[i-1]*(1-p[i]);
l3[i]/p[i]代表的其实是确定了i位为1后的i位的期望,就直接用l1l2求就好,发现顺便把上式中的l3[i-1]消了,所以不需要求l3数组(貌似三个都不需要)。
一路递推ans数组即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int dian=;
double aa[dian],ans[dian],l1[dian],l2[dian];
int n;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf",&aa[i]);
for(int i=;i<=n;i++)
l1[i]=(l1[i-]+)*aa[i];
for(int i=;i<=n;i++)
l2[i]=(l2[i-]+*l1[i-]+)*aa[i];
for(int i=;i<=n;i++)
ans[i]=ans[i-]+(*l2[i-]+*l1[i-]+)*aa[i];
printf("%.1f",ans[n]);
return ;
}
最新文章
- Qt基本框架介绍
- hybrid app
- poj1733Parity game
- 黄聪:如何用Jquery或者插件解除网页禁用右键复制的限制(转)
- Implementation Documentation[转]
- visual studio 2015常用快捷键
- HDU 4721 Food and Productivity (二分+树状数组)
- Android Recovery模式学习体会
- 项目架构开发:数据访问层之UnitOfWork
- 微信支付生成带logo的二维码
- 刨根问底:if 后怎么就可以跟对象,变量交换写法是语法糖吗?
- PHP一些常用的正则表达式分享给大家
- note10 元组
- WebStorm中常用的快捷键及使用技巧
- OSINT系列:网站信任评估WOT
- 序列化、模块 day21
- javascript 重构alert()
- Javascript的&;&;和||的另类用法
- springboot中使用自定义的properties属性
- spring boot常用注解使用小结