题目描述

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

---

概率dp入门题吧。

令f[i][j]表示Alice拿i分，Bob拿j分时的最优概率。

假设这一轮Alice选择难度为p的任务，且2^p=k。

显然有

f[i][j]=f[i+k][j]/4k+f[i+k][j+1]/4k+f[i][j+1]∗(2k−1)/4k+f[i][j]∗(2k−1)/4kf[i][j]=f[i+k][j]/4k+f[i+k][j+1]/4k+f[i][j+1]∗(2k−1)/4k+f[i][j]∗(2k−1)/4k

合并同类项之后变成了：

f[i][j]=(f[i+k][j]+f[i+k][j+1]+f[i][j+1]∗(2k−1))/(2k+1)f[i][j]=(f[i+k][j]+f[i+k][j+1]+f[i][j+1]∗(2k−1))/(2k+1)

代码：

#include
    
     #define N 505using namespace std;int n;double f[N][N];int main(){    cin>>n;    for(int i=0;i<=n;++i)f[n][i]=1.0;    for(int i=n-1;i>=0;--i)        for(int j=n-1;j>=0;--j){            double tmp=0.0;            for(int k=1;k/2<=n;k<<=1){                int l=min(k+i,n);                tmp=max(tmp,(f[l][j]+f[l][j+1]+f[i][j+1]*(2*k-1))/(2*k+1));            }            f[i][j]=tmp;        }    printf("%lf",f[0][0]);    return 0;}