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;    
}
 

相关内容

热门资讯

10分钟辅助挂!搜圈麻将假不假... 10分钟辅助挂!搜圈麻将假不假“详细透视辅助助手教程”原来真的有挂,您好,搜圈麻将假不假这款游戏可以...
记者发布!福建十三水 辅助器(... 记者发布!福建十三水 辅助器(透视)透视辅助神器(2023已更新)(哔哩哔哩);1、福建十三水 辅助...
6分钟实锤!博雅红河棋盘外 挂... 您好,博雅红河棋盘外 挂这款游戏可以开挂的,确实是有挂的,需要了解加微【757446909】很多玩家...
八分钟辅助挂!微乐陕西麻将小程... 八分钟辅助挂!微乐陕西麻将小程序有猫腻吗“详细透视辅助脚本教程”原来真的有挂1、下载好微乐陕西麻将小...
必备科技!多乐够级捕鱼辅助软件... 必备科技!多乐够级捕鱼辅助软件(透视辅助)透明挂透视辅助挂(2023已更新)(哔哩哔哩)1、多乐够级...
让我来分享经验!胖猪竞技有外挂... 让我来分享经验!胖猪竞技有外挂没(辅助)确实存在有挂(2026已更新)(哔哩哔哩)胖猪竞技有外挂没辅...
七分钟攻略!七彩云南游戏有外 ... 七分钟攻略!七彩云南游戏有外 挂吗,wePoke原来真的是有挂,wpk教程(有挂细节)1)七彩云南游...
交流学习经验!老友广东麻将来牌... 交流学习经验!老友广东麻将来牌规律(透视)外挂透视辅助插件(2024已更新)(哔哩哔哩)1、在老友广...
13钟辅助挂!闲来贵州麻将可以... 13钟辅助挂!闲来贵州麻将可以挂吗“详细透视辅助app教程”原来真的有挂是一款可以让一直输的玩家,快...
9分钟攻略!乐乐上海麻将有没有... 9分钟攻略!乐乐上海麻将有没有挂,impoker本来有挂,黑科技教程(有挂教程)乐乐上海麻将有没有挂...