游戏
题目描述
Alice 和 Bob 两个人正在玩一个游戏，游戏有很多种任务，难度为 \(p\) 的任务( \(p \in N_{+}\) )，有 \(2^{-p}\) 的概率完成并得到 \(2^{p-1}\) 分，如果完成不了，得 \(0\) 分。
一开始每人都是 \(0\) 分，从 Alice 开始轮流做任务，她可以选择任意一个任务来做； 而 Bob 只会做难度为 \(1\) 的任务。只要其中有一个人达到 \(n\) 分，即算作那个人胜利。求 Alice 采取最优策略的情况下获胜的概率。
输入描述
一个正整数 \(n\)，表示目标分数。
输出描述
一个数，表示 Alice 获胜的概率，保留6位小数。
输入输出样例 #1
输入样例 #1
1
输出样例 #1
0.666667
输入输出样例 #2
输入样例 #2
4
输出样例 #2
0.673185
输入输出样例 #3
输入样例 #3
10
输出样例 #3
0.704883
说明 / 提示
数据范围
- 对于 \(30\)% 的数据，\(n \leq 10\)。
- 对于 \(100\)% 的数据，\(n \leq 500\)。
解题报告
一开始连题都没读懂 \(\cdots \cdots\)
首先显然，这个 \(p\) 的范围并不需要达到无限，只需要选到第一个满足 \(2^{p-1} \geq n\) 的 \(p\) 就好了，在选更大的 \(p\) 也是可以一次行动获得胜利，而且概率还更低。
我们把先手和后手各行动一次当成一局，设 \(dp[i][j]\) 表示当前先手是 \(i\) 分且后手是 \(j\) 分时，先手胜利的概率。
当先手选择任务 \(p\) 时，考虑一局游戏的所有情况：
- 先手和后手都输了，先手胜利的概率为 \((1-\dfrac 1 2)\times(1-\dfrac{1}{2^p}) \times dp[i][j]\)。
- 先手赢且后手输了，先手胜利的概率为 \((1-\dfrac 1 2)\times\dfrac{1}{2^p} \times dp[i+2^{p-1}][j]\)。
- 先手输且后手赢了，先手胜利的概率为 \(\dfrac 1 2 \times（1-\dfrac{1}{2^p}) \times dp[i][j+1]\)。
- 先手和后手都赢了，先手胜利的概率为 \(\dfrac 1 2 \times \dfrac{1}{2^p} \times dp[i+2^{p-1}][j+1]\)。
当且仅当 \(i \geq n\) 时，\(dp[i][j]=1\)；当且仅当 \(i < n\) 且 \(j \geq n\) 时，\(dp[i][j]=0\)。
一个问题：这里是否要考虑先手直接获胜从而没有后手操作的情况？不需要，我们的第二种情况和第四种情况之和与其等价。
于是当先手选择任务 \(p\) 时，$ dp[i][j]=\dfrac { dp[ i+2^{p-1} ][ j+1 ]+dp[ i+2^{p-1} ][ j ]+ (2^p-1) dp[ i ][ j+1 ] + ( 2^p-1 ) dp[ i ][ j ]} { 2^{p+1} }$。
由于这里存在自己推出自己，我们需要变形分离 \(dp[i][j]\)。
由于先手会取最最优策略，我们需要求出取所有 \(p\) 中的最大值。
设 \(f(p,i,j)=\dfrac{dp[i+2^{p-1}][j+1]+dp[i+2^{p-1}][j]+(2^p-1)dp[i][j+1]}{2^p+1}\) 。
那么 \(dp[i][j] = \max_{2^p\leq 2 \times n} f(p,i,j)\)。
然后可以用记忆化搜索或者直接递推来求解了，注意记搜的过程中不要定义任何变量，否则很容易爆栈。
时间复杂度 \(O(n^2 \log n)\)，代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=511;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int n,m;
double dp[N][N];double dfs(int i,int j)
{if(i>=n) return 1;if(j>=n) return 0;if(dp[i][j]!=-1.0) return dp[i][j];for(int k=1;k<=2*n;k<<=1)ckmax(dp[i][j],( dfs(i+k,j)+dfs(i+k,j+1)+(2*k-1)*dfs(i,j+1) )/(2*k+1));return dp[i][j];
}signed main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);n=read();for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=-1.0;printf("%.6lf\n",dfs(0,0));
/*// 线性求解for(int i=0;i<=n;i++) dp[n][i]=1;for(int i=n-1;i>=0;i--)for(int j=n-1;j>=0;j--){double tmp=0;for(int k=1;k<=2*n;k<<=1){int t=min(n,k+i);double p=(dp[t][j]+dp[t][j+1]+(2*k-1)*dp[i][j+1])/(2*k+1);ckmax(tmp,p);}dp[i][j]=tmp;}printf("%.6lf\n",dp[0][0]);
*/// debug
/*for(int i=0;i<=n;i++,putchar('\n'))for(int j=0;j<=n;j++,putchar(' '))cout<<dp[i][j];
*/return 0;
}