OSU!题解(概率dp)
创始人
2025-01-08 19:03:32
0次

题目:OSU! - 洛谷

思路:

设E(x_{i})表示截止到i所获得的分数;

对于到i点的每一个l,如果第i+1点为1,那么会新增分数3*l^2+3*l+1;

就有递推公式方程:

E(x_{i+1})=E(x_{i})+p[i+1]\sum_{0}^{i}p*(3*l^2+3*l+1);(p代表截止到i获得长度l的概率);

得:

E(x_{i+1})=E(x_{i})+p[i+1]*(3*E(l_{i}^{2})+3*E(l_{i})+1);

E(l_{i+1}^{2})=p[i+1]*(E(l_{i}^{2})+2*E(l_{i})+1);

E(l_{i+1})=p[i+1]*(E(l_{i})+1);

不断更新这三个值;

代码:

#include
using namespace std;
#define LL long long
const int N = 1e5 + 10;
double x,y,z;
double p[N],n;
int  main() {
  cin>>n;
  for(int i=1;i<=n;i++) cin>>p[i];
  for(int i=1;i<=n;i++)
  {  
     x+=p[i]*(3*y+3*z+1);
     y=p[i]*(y+2*z+1);     
       z=p[i]*(z+1);
  }
  printf("%.1f\n",x);
  
    return 0;    
}
 

相关内容

热门资讯

一分钟了解辅助!新518互游辅... 一分钟了解辅助!新518互游辅助多功能AI软件,新518互游真是真的是有辅助软件1、新518互游辅助...
终于清楚开挂!卡米大厅开挂多功... 终于清楚开挂!卡米大厅开挂多功能AI方法,卡米大厅其实存在有开挂方法1、下载好卡米大厅正确养号方法之...
六分钟了解作弊器!玄灵大厅作弊... 六分钟了解作弊器!玄灵大厅作弊器多功能AI软件,玄灵大厅真是有作弊器软件1、很好的工具软件,可以解锁...
一起来讨论外挂!椰子大厅外挂多... 一起来讨论外挂!椰子大厅外挂多功能AI攻略,椰子大厅原来是真的有外挂攻略1、椰子大厅辅助软件下载优化...
玩家必看教程辅助!鲨鱼众娱辅助... 玩家必看教程辅助!鲨鱼众娱辅助多功能AI攻略,鲨鱼众娱一直真的是有辅助攻略1、许多玩家不知道鲨鱼众娱...
盘点一款开挂!皇豪大厅开挂多功... 盘点一款开挂!皇豪大厅开挂多功能AI攻略,皇豪大厅确实是真的有开挂攻略1、进入到皇豪大厅是否有挂之后...
教学盘点辅助器!老夫子大厅辅助... 教学盘点辅助器!老夫子大厅辅助器多功能AI攻略,老夫子大厅竟然真的是有辅助器攻略1、该软件可以轻松地...
热点推荐透视挂!嗨玩娱乐麻将透... 热点推荐透视挂!嗨玩娱乐麻将透视挂多功能AI软件,嗨玩娱乐麻将本来真的是有透视挂软件1、下载好嗨玩娱...
一分钟揭秘作弊器!黑莓大厅作弊... 一分钟揭秘作弊器!黑莓大厅作弊器多功能AI教程,黑莓大厅本来是真的有作弊器教程1、首先打开黑莓大厅辅...
玩家必看科普开挂!七天娱乐开挂... 玩家必看科普开挂!七天娱乐开挂多功能AIapp,七天娱乐竟然存在有开挂app1、七天娱乐公共底牌简单...