题目传送门
题目描述
公主和龙🐉从一个初始装有 w 只白老鼠和 b 只黑老鼠的袋子中轮流抓老鼠，第一个从袋子里抓出白老鼠的人获胜。每一次龙从袋子里抓出一只老鼠时其他在袋子里的老鼠会变得惊慌，其中的一只会跳出袋子（公主抓老鼠时不会有老鼠跳出）。公主先手。公主获胜的概率是多少？另外，如果袋子里已经没有任何老鼠且没有一个人抓出了一只白老鼠，则龙获胜。自己跳出袋子的老鼠不是被抓出来的（不能决定胜者）。一只老鼠离开袋子后将永不返回袋子中。所有袋子中的老鼠被抓出去的概率是相等的，所有袋子中的老鼠受到惊吓跳出袋子的概率也是相等的。
思路
很适合刚学概率 DP 的人练练手！很有意思。
我们设 f[i][j] 表示在有 i 只白老鼠和 j 只黑老鼠时公主先手的获胜概率，g[i][j] 表示龙🐉先手的获胜概率。于是就有转移：
f[i][j] = i/(i+j) + j/(i+j)*(1-g[i][j-1])，即一次就抓到白老鼠和抓到黑老鼠但龙🐉输了的概率和。
g[i][j] = i/(i+j) + [j/(i+j)]*[i/(i+j-1)]*(1-f[i-1][j-1]) + [j/(i+j)]*[(j-1)/(i+j-1)]*(1-f[i][j-2])，即一次抓到白老鼠，抓到黑老鼠跑了白老鼠时公主输了，抓到黑老鼠跑了黑老鼠时公主输了的概率和。
于是一个非常简短的代码就诞生了。
Code
#include<bits/stdc++.h>
using namespace std;
double f[1005][1005],g[1005][1005];// f[i][j] 表示 i 只白老鼠和 j 只会给老鼠时公主的获胜概率，g[i][j] 同理。
int main(){int w,b;scanf("%d%d",&w,&b);for(int i=1;i<=w;i++){f[i][0]=g[i][0]=1; //记得处理边界条件。for(int j=1;j<=b;j++){f[i][j]=1.0*i/(i+j)+1.0*j/(i+j)*(1-g[i][j-1]);g[i][j]=1.0*i/(i+j)+1.0*j/(i+j)*i/(i+j-1)*(1-f[i-1][j-1]);if(j>=2) g[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*(1-f[i][j-2]); //判断下标是否会越界。}}printf("%.9lf\n",f[w][b]); return 0;
}
\(\sim\) ❀完结撒花❀ \(\sim\)