【bzoj3191】[JLOI2013]卡牌游戏 概率dp
游戏 DP 概率
2023-09-11 14:22:39 时间
题目描述
n个人围成一圈玩游戏,一开始庄家是1。每次从m张卡片中随机选择1张,从庄家向下数个数为卡片上的数的人,踢出这个人,下一个人作为新的庄家。最后一个人获胜。问每个人获胜的概率。
输入
第一行包括两个整数N,M分别表示玩家个数和卡牌总数。
接下来一行是包含M个整数,分别给出每张卡片上写的数字。
输出
输出一行包含N个百分比形式给出的实数,四舍五入到两位小数。分别给出从玩家1到玩家N的胜出概率,每个概率之间用空格隔开,最后不要有空格。
样例输入
5 5
2 3 5 7 11
样例输出
22.72% 17.12% 15.36% 25.44% 19.36%
题解
概率dp
设$f[i][j]$表示$i$个人游戏$j$获胜的概率,那么考虑转移:
枚举选择了哪张卡片,然后看$j$是否被踢出,如果没被踢出则再计算它是新一局游戏的第几个即可。
算第几个时略微有点复杂,可以在纸上画画,推一下可知如果踢出$t$,那么新一轮$j$的位置为$(j-t+i-1)\%i+1$。
即状态转移方程为$f[i][j]=\sum\limits_{k=1}^m[t\neq j]·\frac{f[i - 1][(j-t+i-1)\%i+1]}m$。
最后的答案就是$f[n][i]$,注意格式问题,最后不能有空格。
时间复杂度$O(n^3)$
#include <cstdio> #define N 55 double f[N][N]; int a[N]; int main() { int n , m , i , j , k , t; scanf("%d%d" , &n , &m); for(i = 1 ; i <= m ; i ++ ) scanf("%d" , &a[i]); f[1][1] = 100; for(i = 2 ; i <= n ; i ++ ) for(j = 1 ; j <= i ; j ++ ) for(k = 1 ; k <= m ; k ++ ) if((t = (a[k] - 1) % i + 1) != j) f[i][j] += f[i - 1][(j - t + i - 1) % i + 1] / m; for(i = 1 ; i < n ; i ++ ) printf("%.2lf%% " , f[n][i]); printf("%.2lf%%\n" , f[n][n]); return 0; }
相关文章
- 动态规划(DP)之多边形游戏问题
- 未成年帐号登录华为游戏,启动后不断弹出防沉迷提示
- 《C++游戏编程入门(第4版)》——2.7 使用do循环
- 《Python和Pygame游戏开发指南》——2.21 抗锯齿
- 《Android游戏开发详解》——第1章,第1.4节关于位的一切(位和字节的简单介绍)
- macOS 电脑上通过AI生成游戏角色基于Stable Diffusion(教程含源码)
- 华为联运游戏或应用审核驳回:使用花币充值时,对支付延时处理不当,导致商品不到账2021-05-24
- 华为快游戏调用登录接口失败,返回错误码 -1
- 小学生python游戏编程arcade----基本知识2
- 小学生python游戏编程arcade----基本知识1
- 探讨 使用GWT 做一个web游戏。如何设计一个web游戏。
- 关于Unity中ARPG游戏人物移动(专题十一)
- 【游戏开发】自从遇见了口袋方舟后,我的世界变得精彩了起来
- 【uoj#51】[UR #4]元旦三侠的游戏 博弈论+dp
- 【loj6191】「美团 CodeM 复赛」配对游戏 概率期望dp
- 【bzoj1775】[Usaco2009 Dec]Vidgame 电视游戏问题 dp