Alice 与 Bob 的游戏 （概率DP)

题目描述
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

由题意可知：
1、只要有一人的分数大于等于n就胜出；
2、对于Alice 每次选分数为k的任务，成功的概率为 1/2*k，失败的概率为(1-1/2*k);
3、对于Bob 每次只能选分数为1的任务，成功与失败的概率均为 1/2。

首先确定状态，f[i][j] 为Alice 为 i 分，Bob 为 j 分，Alice要取胜的概率；

然后我们发现可以倒着往前推,先初始化 f[n][] =1，然后由f[n][n] 每次减一个分数；
每次做任务分四种情况：

1、Alice 选择 得分为 k 的任务，成功，Bob 选择得分为1的任务，也成功了，则：
—-f[ii][j]=f[i+k][j+1]/2*k/2;
2、Alice 选择 得分为 k 的任务，成功，Bob 选择得分为1的任务，但没有成功则：
—f[i][j]=f[i+k][j]/2*k/2;
3、Alice 选择 得分为 k 的任务，没有成功，Bob 选择得分为1的任务，成功了，则：
—-f[i][j]=f[i][j+1]*(1-1/2*k)/2;
4、Alice 选择 得分为 k 的任务，没有成功，Bob 选择得分为1的任务，也没成功了，则：
—–f[i][j]=f[i][j]*(1-1/2*k)/2;

f[i][j] 的值就等于上面四项之和 ，化简的方程：
f[i][j]=(f[l][j+1]/k/4+f[l][j]/k/4+f[i][j+1](k*2-1)/k/4)/(1.0-1.0(k*2-1.0)/k/4);

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<iomanip>
#include<iostream>
#include<cctype>
#include<algorithm>
#define esp 1e-8
using namespace std;
int n;
double f[505][505],tmp,val;
//---------------------
int main()
{
    scanf("%d",&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--){
        val=0;
        for(int k=1;k/2<=n;k<<=1){ // k>=2*n 可能答案更优，比如 n=1,k=2就可以一次胜出
            int l=i+k;  
            if(l>n) l=n;
            double p=1.0/(k*2.0);
            double P=(1.0)/(2.0*k+1.0);
            tmp=f[l][j+1]*P+f[l][j]*P+(1.0-p)*f[i][j+1]/(p+1.0);
            if(tmp>val) val=tmp;
        }f[i][j]=val;
    }
    cout.setf(ios::fixed); 
    cout<<fixed<<setprecision(6)<<f[0][0]<<endl;
    return 0;
}