[水题]终极简单问题

题目大意:两个人玩牌,他们各有m(<=100)张牌,输入牌上的数字(<=50),有n(<=50)轮回合,每回合他们从自己牌中随机选1张,牌上的数字加入答案后放回牌组中。问n回合后第一个人赢的概率是多少(保留6位小数)?

我当时居然还想随机模拟最后输出答案(显然精度不够),然而随机数生成我用的是rand*rand(),搞得分布都不均了(降智打击)

别的不管,这肯定是一道dp题,考虑到数据范围,我们可以这样设计状态。

\(A[i][j]\)表示第一个人在第i轮选到的牌的总和是j的概率,\(B[i][j]\)是第二个人的。

由于每轮我们抽到每张牌的概率是均等的,所以我们可以用 (上一轮的状态+每张卡的值)/m 来更新当前状态。

然后我们用\(sb[i]\)来表示第二个人总和小于i的概率,\(sb[i]=sb[i-1]+B[n][i-1]\),最后枚举i,将\(A[n][i]\times sb[i]\)累加进答案。

代码

3 thoughts to “[水题]终极简单问题”

发表评论

电子邮件地址不会被公开。 必填项已用*标注