【loj6191】「美团 CodeM 复赛」配对游戏 概率期望dp
2023-09-11 14:22:39 时间
题目描述
n次向一个栈中加入0或1中随机1个,如果一次加入0时栈顶元素为1,则将这两个元素弹栈。问最终栈中元素个数的期望是多少。
输入
一行一个正整数 n 。
输出
一行一个实数,表示期望剩下的人数,四舍五入保留三位小数。
样例输入
10
样例输出
4.168
题解
概率期望dp
显然任何时刻栈中的元素自底至顶一定是若干个0+若干个1。
但是如果设状态$p[i][j][k]$表示前$i$次操作,栈中$j$个0,$k$个1的概率,复杂度是$O(n^3)$的,显然会TLE。
注意到$0$的个数对状态转移是没有影响的,而期望在任何时刻都具有可加性,因此可以设$f[i][j]$表示前$i$次操作,栈中$j$个1的期望元素个数。
那么直接考虑新加入一个是0还是1,看一下长度是增加还是减少即可。
这里有一个问题:每次增加或减少的长度是多少?由于我们设的是总情况的期望,而期望等于 概率*权值 ,这种情况的权值为1,因此期望值就是这种情况的概率。
所以还需要维护一个$p[i][j]$表示前$i$次操作,栈中$j$个1的概率。每次使用概率转移期望即可。
时间复杂度$O(n^2)$
#include <cstdio> #define N 2010 double p[N][N] , f[N][N]; int main() { int n , i , j; double ans = 0; scanf("%d" , &n) , p[0][0] = 1; for(i = 0 ; i < n ; i ++ ) { p[i + 1][1] += p[i][0] / 2 , f[i + 1][1] += (f[i][0] + p[i][0]) / 2; p[i + 1][0] += p[i][0] / 2 , f[i + 1][0] += (f[i][0] + p[i][0]) / 2; for(j = 1 ; j < n ; j ++ ) { p[i + 1][j + 1] += p[i][j] / 2 , f[i + 1][j + 1] += (f[i][j] + p[i][j]) / 2; p[i + 1][j - 1] += p[i][j] / 2 , f[i + 1][j - 1] += (f[i][j] - p[i][j]) / 2; } } for(i = 0 ; i <= n ; i ++ ) ans += f[n][i]; printf("%.3lf\n" , ans); return 0; }
相关文章
- AWS上的游戏服务:Lumberyard + Amazon GameLift + Twitch
- [cocos2d-x]怎样降低cocos2d-x游戏的耗电量?
- 基于FPGA的汉诺塔游戏
- 有奖征集活动系列——【HTML5游戏编程之旅】已结束
- 华为联运游戏审核驳回:无法进入游戏,但开发者自己测试登录正常
- 《游戏大师Chris Crawford谈互动叙事》一1.7 本章小结
- 《游戏大师Chris Crawford谈互动叙事》一22.2 消极的预测
- 《Cocos2D-X游戏开发技术精解》一1.3 引擎的版本
- 《Unity 3.x游戏开发实例》——2.5节机制VS主题
- 【2023unity游戏制作-mango的冒险】-6.关卡设计
- 华为OD机试 - 消消乐游戏(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 手把手讲解超详细python入门游戏项目‘打外星飞船’(三)
- 【历史上的今天】2 月 21 日:Spotify 创始人出生;《塞尔达传说》系列诞生;游戏门户网站 GameSpy 关闭
- 探讨 使用GWT 做一个web游戏。如何设计一个web游戏。