D - Darts Gym - 102470D（概率DP，博弈）

题意： 两个人在飞镖射击，射到不同地方有不同分数，分数先到0则获胜。 A随机射击，B指定一个位置，最终射击结果为这个位置和相邻两个位置。 求A先手和B先手的获胜概率。

思路： 记忆化搜索，两个人分数都小于等于20的时候，结果肯定是固定的，因为射击到分数大的分数不变，分数小的状态也不变，只有是射击到刚好自己分数的时候，才会获胜。

定义$f[i][j][0/1]$为A分数为i，B分数为j，并且A(B)先手时候的获胜概率。

转移就是每次枚举自己射击的那个位置。

不过本题比较奇特的是 $f[i][j][0]$由$f[i][j][1]$转移过来，而$f[i][j][1]$也由$f[i][j][0]$转移过来，谁先谁后怎么判断？

赛中的时候我们是在dfs里面弄了个层次变量，代表如果到了很深的层次（比如1000），就直接退出。

但事实上如果$i\ge 20$且$j\ge 20$，两个人操作分数都会变， 如果$i\ge 20$且$j<20$，那么A的分数会变，B可能不会变，所以只存在$f[i][j][1]$由$f[i][j][0]$转移过来，所以先计算A先手的概率。 如果$i<20,j\ge 20$，同理，先计算B先手的概率。 如果$i\le 20,j\le 20$，此时两种转移都可能发生，但是我们可以通过预处理算出这部分的概率。

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #include <map> using namespace std; double dp[505][505][2]; int vis[505][505][2]; int num[20] = {1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5,20}; double dfs(int x,int y,int flag) { if(vis[x][y][flag]) return dp[x][y][flag]; double win = 0.0; if(flag) { for(int i = 0;i < 20;i++) { int now = num[i]; if(now > x) { win += (1.0 - dfs(x,y,flag ^ 1)) / 20.0; } else if(now == x) { win += 1.0 / 20.0; } else { win += (1.0 - dfs(x - now,y,flag ^ 1)) / 20.0; } } } else { for(int i = 0;i < 20;i++) { double tmp = 0.0; for(int k = 0;k < 3;k++) { int now = num[(i + k) % 20]; if(now > y) tmp += (1 - dfs(x,y,flag ^ 1)) / 3.0; else if(now == y) tmp += 1.0 / 3.0; else tmp += (1.0 - dfs(x,y - now,flag ^ 1)) / 3.0; } win = max(win,tmp); } } vis[x][y][flag] = 1; return dp[x][y][flag] = win; } int main() { int n; for(int i = 1;i <= 20;i++) { for(int j = 1;j <= 20;j++) { dp[i][j][0] = 0.909090909091; dp[i][j][1] = 0.136363636364; vis[i][j][0] = vis[i][j][1] = 1; } } while(~scanf("%d",&n) && n) { printf("%.10f %.10f\n",dfs(n,n,1),dfs(n,n,0)); } return 0; }