stdKonjac's Blog

 要做到不可替代,就要与众不同。

【游戏】

题目描述

Alice 和 Bob 两个人正在玩一个游戏,游戏有很多种任务,难度为 p 的任务(p是正整数),有 1/(2^p) 的概率完成并得到 2^(p-1) 分,如果完成不了,得 0 分。一开始每人都是 0 分,从 Alice 开始轮流做任务,她可以选择任意一个任务来做;而 Bob 只会做难度为 1 的任务。只要其中有一个人达到 n 分,即算作那个人胜利。求 Alice 采取最优策略的情况下获胜的概率。

输入格式

一个正整数 n ,含义如题目所述。

输出格式

一个数,表示 Alice 获胜的概率,保留 6 位小数。

样例数据 1

输入

1

输出

0.666667

备注

【数据范围】
对于 30% 的数据,n≤10
对于 100% 的数据,n≤500

这道题再次证明了遇到计算概率必爆0的定律,考场上看都没看懂题……

好吧说正解,其实是一道DP题,用dp[i][j]表示A(Alice)得i分,B(Bob)得j分的最优策略时的获胜概率对于第i+1次决策,一定是由第i次的四种情况转移而来,既A胜B胜,A胜B败,A败B胜,A败B败,即:

dp[i][j]=1/2k*1/2*dp[i+2k-1][j+1]+1/2k*1/2*dp[i+2k-1][j]+(1-1/2k)*1/2*dp[i][j+1]+(1-1/2k)*1/2*dp[i][j],因为要推dp[i][j]所以把最后一项移过去就行了,其中1/2可以约分掉,约不约随便吧。

下面是代码:

 

点赞

发表评论

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

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.